[Baekjoon Online Judge] 9095번: 1, 2, 3 더하기

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보다 작다.

출력

 - 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

 특정한 규칙을 가지고 있는지 찾아보기 위해 n의 값을 1부터 구해보았다.

 

n	1, 2, 3의 합으로 나타내는 방법	총 개수
1	1	1
2	1+1, 2	2
3	1+1+1, 1+2, 2+1, 3	4
4	1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1	7
5	1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 2+3, 3+2, 1+1+3, 1+3+1, 3+1+1, 2+2+1, 2+1+2, 1+2+2	13
6	1+1+1+1+1, 1+1+1+1+2, 1+1+1+2+1, 1+1+2+1+1, 1+2+1+1+1, 2+1+1+1+1, 1+1+2+2, 1+2+1+2, 1+2+2+1, 2+1+2+1, 2+2+1+1, 2+1+1+2, 1+1+1+3, 1+1+3+1, 1+3+1+1, 3+1+1+1, 1+2+3, 1+3+2, 2+3+1, 3+2+1, 3+1+2, 2+1+3, 3+3, 2+2+2	24

 총 개수를 나열해보면 1, 2, 4, 7, 13, 24 ... 인 것을 알 수 있다. f(n)을 n을 1, 2, 3의 합으로 나타낸 총 개수라고 가정하면, f(4) = f(3) + f(2) + f(1) 이고, f(5) = f(4) + f(3) + f(2) 인 것을 알 수 있다.

 

 위 식을 간단하게 식으로 정리해보았다.

 

n = 1 일때 f(1) = 1
n = 2 일때 f(2) = 2
n = 3 일때 f(3) = 4
n이 3보다 크면, f(n) = f(n - 1) + f(n - 2) + f(n - 3)

 

 큰 문제에 작은 문제가 들어 있기 때문에 다이나믹 프로그래밍으로 해결 가능하다. 

 

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

public class Baekjoon9095 {

    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(bufferedReader.readLine());

        dp = new int[11]; // n은 양수이며 11보다 작다. 0 ~ 10

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        dp[4] = 7;

        for (int i = 5; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp [i - 3];
        }

        for (int i = 0; i < t; i++) {
            int num = Integer.parseInt(bufferedReader.readLine());
            bufferedWriter.write(dp[num] + "\n");
        }

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}