[백준 JAVA] 15989 : 1, 2, 3 더하기 4

[백준 15989] 1, 2, 3 더하기 4 : https://www.acmicpc.net/problem/15989

---

문제 조건 정리

 

1. 정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

입력

 

1. 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
2. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.
   n은 양수이며 10,000보다 작거나 같다.

 

---

문제를 풀기 전

 

1. 합을 이루는 수들의 수열을 오름차순으로 배치한다면 중복 문제를 해결할 수 있을 것으로 예상함.
2. 1차원 배열로 나타내려고 하니 자꾸 막힘.
3. 2차원 배열로 나타냈음.
   10000까지의 숫자를 (1 ~ 3)의 합으로 나타내는 오름차순 수열 
   -> dp[10001][4]
   
   dp[x][1] = x를 만드는데 1로 끝나는 오름차순 수열
   -> 1이 x개 -> 반드시 1 뿐
   -> dp[x-1][1] 뒤에 1
   -> dp[x-1][1]
   
   dp[x][2] = x를 만드는데 2로 끝나는 오름차순 수열
   -> 1, 2로 시작해서 2로 끝남
   -> dp[x-2][1] 뒤에 2 , dp[x-2][2] 뒤에 2
   -> dp[x-2][1] + dp[x-2][2]
   
   dp[x][3] = x를 만드는데 3로 끝나는 오름차순 수열
   -> 1, 2, 3으로 시작해서 3으로 끝남
   -> dp[x-3][1] 뒤에 3, dp[x-3][2] 뒤에 3, dp[x-3][3] 뒤에 3
   -> dp[x-3][1] + dp[x-3][2] + dp[x-3][3]
   
   

---

코드

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ15989 {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bufferedReader.readLine());
        int[][] counts = new int[10001][4];
        counts[1][1] = 1; // 1을 만들고 마지막이 1 -> 1+1

        counts[2][1] = 1; // 1+1
        counts[2][2] = 1; // 2

        counts[3][1] = 1; // 1+1+1, 2+1(오름차순이 아니라서 카운트 x)
        counts[3][2] = 1; // 1+2
        counts[3][3] = 1; // 3
        // 여기까지만 초기화해도 됨

        counts[4][1] = 1; // 1+1+1+1                    -> counts[3][1]+1,
        counts[4][2] = 2; // 1+1+2, 2+2                 -> counts[2][1]+2, counts[2][2]+2
        counts[4][3] = 1; // 1+3                        -> counts[1][1]+3
        // counts[4][4] = x; // 4부터 불가능

        counts[5][1] = 1; // 1+1+1+1+1                  -> counts[4][1]+1
        counts[5][2] = 2; // 1+1+1+2, 1+2+2             -> counts[3][1] + 2, counts[3][2] + 2
        counts[5][3] = 2; // 1+1+3, 2+3                 -> counts[2][1] + 3, counts[2][2]+3

        counts[6][1] = 1; // 1+1+1+1+1+1                -> counts[5][1] + 1
        counts[6][2] = 3; // 1+1+1+1+2, 1+1+2+2, 2+2+2  -> counts[4][1] + 2, counts[4][2] + 2
        counts[6][3] = 3; // 1+1+1+3, 1+2+3, 3+3        -> counts[3][1] + 3, counts[3][2] + 3, counts[3][3] + 3

        StringBuilder stringBuilder = new StringBuilder();

        for (int tc = 0; tc < t; tc++) {
            int n = Integer.parseInt(bufferedReader.readLine());
            if (counts[n][1] == 0) {
                for (int i = 6; i <= n; i++) {
                    counts[i][1] = counts[i-1][1];
                    counts[i][2] = counts[i-2][1] + counts[i-2][2];
                    counts[i][3] = counts[i-3][1] + counts[i-3][2] + counts[i-3][3];
                }
            }
            stringBuilder.append(counts[n][1] + counts[n][2] + counts[n][3]).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

 

---

문제를 풀고 난 후

 

dp 어렵다.. 1차원 배열로 해결하려고 고민 많이 했었는데, 2차원 배열 풀이 눈 흘깃~ 한번 보고 풀었다.

익숙해질 때까지 익숙해져야지.