[Java] 백준 15989번 - 1,2,3 더하기 4 (dp, 다이나믹 프로그래밍)

문제 링크 : https://acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

 

문제

정수 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

---

 

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

 

[2] 

1 + 1

=> 1가지

 

[3]

1 + 1 + 1

2 + 1

=> 2가지

 

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

 

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

 

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

 

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

 

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)

(3 + 3 + 1 + 1), (3 + 3 + 2)

=> 10가지

 

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)

(3 + 3 + 3)

=> 12가지

 

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)

(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)

(3 + 3 + 3 + 1)

=> 14가지

 

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)

(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)

=> 16가지

 

0	1	2	3	4	5	6	7	8	9	10
0	0	1	2	4	5	6	8	10	12	14

 

 

6부터 2씩 증가-> fail!!!

 

 

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

dp[n,1]을 구해보자.		dp[n,2]을 구해보자.		dp[n,3]을 구해보자.
1	1	dp[1,2] : 1, 2을 활용해 1을 만드는 방법의 수 1	1	dp[1,3] : 1, 2, 3을 활용해 1을 만드는 방법의 수 1	1
1 + 1	1	dp[2,2]  : 1, 2를 활용해 2을 만드는 방법의 수 1 + 1	1	dp[2,3] : 1, 2, 3을 활용해 2을 만드는 방법의 수 1 + 1 2	2
1 + 1 + 1	1	dp[3,2] : 1, 2를 활용해 3을 만드는 방법의 수 1 + 1 + 1 2 + 1	2 = dp[3,1] + 1	dp[3,3] : 1, 2, 3을 활용해 3을 만드는 방법의 수 1 + 1 + 1 2 + 1 3	3
1 + 1 + 1 + 1	1	dp[4,2] : 1, 2를 활용해 4를 만드는 방법의 수 1 + 1 + 1 + 1 2 + 1 + 1 2 + 2	3 = dp[4,1] + 2	dp[4,3] : 1, 2, 3을 활용해 4을 만드는 방법의 수 1 + 1 + 1 + 1 2 + 1 + 1 2+ 2 3 + 1	4 = dp[4,2] + 1
1 + 1 + 1 + 1 + 1	1	dp[5,2] : 1, 2를 활용해 5를 만드는 방법의 수 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1	3 = dp[5,1] + 2	dp[5,3] : 1, 2, 3을 활용해 5을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2+ 2 + 1 3 + 1 + 1 3 + 2	5 = dp[5,2] + 2
1 + 1 + 1 + 1 + 1 + 1	1	dp[6,2] : 1, 2를 활용해 6을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 2 + 2 + 2	4 = dp[6,1] + 3	dp[6,3] : 1, 2, 3을 활용해 6을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1  2 + 1 + 1 + 1 + 1  2 + 2 + 1 + 1   2 + 2 + 2 3 + 1 + 1 + 1 3 + 2 + 1 3 + 3	7 = dp[6,2] + 3
1 + 1 + 1 + 1 + 1 + 1 + 1	1	dp[7,2] : 1, 2를 활용해 7을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 1	4 = dp[7,1] + 3	dp[7,3] : 1, 2, 3을 활용해 7을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1  2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 1 3 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 3 + 2 + 2 3 + 3 + 1	8 = dp[7,2] + 4
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1	1	dp[8,2] : 1, 2를 활용해 8을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2	5 = dp[8,1] + 4	dp[8,3] : 1, 2, 3을 활용해 8을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 3 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 3 + 2 + 2 + 1 3 + 3 + 1 + 1 3 + 3 + 2	10 = dp[8,2] + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1	1	dp[9,2] : 1, 2를 활용해 9을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1	5 = dp[9,1] + 4	dp[9,3] : 1, 2, 3을 활용해 9을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 3 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 3 + 2 + 2 + 2 3 + 3 + 1 + 1 + 1 3 + 3 + 2 + 1 3 + 3 + 3	12  = dp[9,2] + 7
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1	1	dp[10,2] : 1, 2를 활용해 10을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2	6 = dp[10,1] + 5	dp[10,3] : 1, 2, 3을 활용해 10을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 3 + 3 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 3 + 3 + 2 + 2 3 + 3 + 3 + 1	14 = dp[10,2] + 8
		dp[15,2] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1	8 = dp[15,1] + 14	dp[15,3] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 ====== 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 + 1 3 + 2 + 2 + 2 + 2 3 + 3 + 1 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 + 1 3 + 3 + 2 + 2 + 1 3 + 3 + 3 + 1 + 1 3 + 3 + 3 + 2	18
		dp[20,2] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2	11	dp[20,3] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2 ============== 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 + 1 + 1 3 + 2 + 2 + 2 + 2 + 1 3 + 3 + 1 + 1 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 + 1 + 1 3 + 3 + 2 + 2 + 1 + 1 3 + 3 + 2 + 2 + 2 3 + 3 + 3 + 1 + 1 + 1 3 + 3 + 3 + 2 + 1 3 + 3 + 3 + 3

 

• dp[n,1] = 1
• dp[n,2] = n/2(몫만) + 1
• dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]

import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}