춤추는 개발자

문제 출처 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 접근 방식 및 풀이 - 다이나믹 프로그래밍 (DP) 의 기본 문제 - 재 사용할수 있는 부분을 구하여, 그다음 숫자..

문제 출처 https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다. www.acmicpc.net 접근 방식 및 풀이 참고 : Baekjoon Online Judge 1451번 풀이 0. 문제 요약 - 직사각형의 크기 : N * M - 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누는 문제 - 모든칸은 하나의 직사각형에 포함되어야한다.(남는 칸이 없어야한다.) - 각 직사..

문제 출처 https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 접근 방식 및 풀이 - BFS, DFS 모두 사용가능하지만, BFS는 알파벳의 방문여부를 체크하기 까다롭다. 이부분에서 해매다가 ..

문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 접근 방식 및 풀이 - BFS와 Deque 개념 활용한 문제 - 핵심 알고리즘은 BFS에서 0이면 그냥 가고, 1이면 부수고 가야하므로 dist 배열에 1을 더해주는 것이다. - 프로그래밍에서 배열과 수학에서의 x, y 좌표.. 가 헷갈려서 중간에 런타임에러 엄청 걸렸다. 소스 코드 1 2 3 4 5 6 7 8 9 ..

문제 출처 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 접근 방식 및 풀이 - 완전탐색(brute force), dfs 사용하여 min 값을 계속 갱신한다. - 참고블로그 : #백준_10971 외판원 순회2 - Java 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

문제 출처 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 예제 입력 1 복 www.acmicpc.net 접근 방식 및 풀이 - 1208번과 비슷한 문제 [Algorithm/백준] - [백준] 1208번 자바 부분수열의 ..

문제 출처 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근 방식 및 풀이 - 투포인트 알고리즘, DFS 활용 하여 해결 할 수 있다. - DFS 알고리즘을 적용하여 지금 위치의 원소를 선택하거, 선택하지 않거나 2가지 조건을 재귀함수로 계속 호출하였다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 출처 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근 방식 및 풀이 - N의 값이 최대 8까지 이므로 배열로 만들수 있는 모든 수열들의 케이스를 조사(순열 개념 적용) - 각 배열로 구한 값들중 가장 큰 값을 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

문제 출처 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근 방식 및 풀이 - 1182와 비슷한 문제라고 생각하는 순간 해맨다. -> 같은 알고리즘을 쓰면 시간 초과 발생 - 여러 블로그들을 참고하여 배열의 크기가 크기때문에, 배열을 반으로 나눠 각각 부분합들을 구해준 후 투포인트 알고리즘으로 해결하라는 힌트를 받았다. 참고 블로그 [백준 알고리즘]1208번 부분수열의 합2 백준 알고리즘 부분수열의 합..

문제 출처 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2 www.acmicpc.net 접근 방식 및 풀이 - 백트래킹 방법, DFS 방법이 있었지만, DFS으로 구현하였다. - DFS로 탐색하다가 6자리 문자열을 다..