백준 15989번 1,2,3 더하기 4(자바) - dp #
1, 2, 3 더하기 4 성공
| 1 초 (추가 시간 없음) | 512 MB | 4825 | 3044 | 2395 | 64.347% |
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.
- 1+1+1+1
- 2+1+1 (1+1+2, 1+2+1)
- 2+2
- 1+3 (3+1)
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력 1 복사
3
4
7
10
예제 출력 1 복사
4
8
14이 문제는 기존 dp 더하기 문제에서 좀 더 업그레이드 된 문제여서 풀이를 생각해내기 어려웠다.
기존 dp 문제에서는 dp[n] = dp[n-1]+dp[n-2]+dp[n-3] 이렇게 풀 수 있었다면
이번 문제에서는 1+1+2 2+1+1을 같은 식으로 보기 때문에 중복을 제거해야 한다.
중복을 제거하기 위해서는 수를 더해줄 때 마지막 숫자보다 큰 수만 더할 수 있도록 하는 방법이 있다.
예를 들어 1+1+2라면 마지막 수가 2이므로 1+1+2+2와 1+1+2+3만 가능하도록 하는 것이다.
풀이
: dp를 2차원 배열로 만들어 dp[n][a]에서 a는 마지막 수를 의미하도록 한다.
그렇게 점화식을 세워보면
dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3] (3번째 전에 있는 수에 3을 더해주면 n이 나오는데 이때 1로 끝나는 배열, 2로 끝나는 배열, 3으로 끝나는 배열 모두에 3을 더해줄 수 있다)
dp[n][2] = dp[n-2][1] + dp[n-2][2] (2번째 전에 있는 수에 2를 더해주면 n이 나오는데 이때 마지막 수가 1,2인 경우에만 2를 더할 수 있다)
dp[n][1] = dp[n-1][1]
이다.
#주의
처음에 dp 크기를 n+1로 설정해서 dp[2]에 1을 넣어줄 때 인덱스 오류가 발생했다.(n이 2보다 작으면 오류)
따라서 그냥 dp 크기를 10001로 설정했다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-->0) {
int n = sc.nextInt();
int[][] dp = new int[10001][4];
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;
for (int i = 4; i <= n; i++) {
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-2][1] + dp[i-2][2];
dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
}
System.out.println(dp[n][1] + dp[n][2] + dp[n][3]);
}
}
}