백준 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]);
        }

    }
}