1,2,3 더하기

문제

정수 4를 1,2,3의 조합으로 나타내는 방법은 총 7가지가 있다.

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의 합으로 나타내는 방법의 수를 출력한다.

예제입력

예제출력

7  
44  
274

점화식

1의 조합일 때

N-1 + 1 = N

2의 조합일 때

N-2 + 2 = N

3의 조합일 때

N-3 + 3 = N

D[N] = D[n-1] + D[n-2] + D[n-3]

마지막에 붙인 수로 경우를 나누기

n을 만드는 순서를 서로 다른 방법으로 센다. 마지막에 1을 붙인 방법은 n−1을 만든 모든 방법에 하나씩 대응하고, 마지막에 2 또는 3을 붙이는 경우도 같다. 세 경우는 마지막 수가 달라 서로 겹치지 않으므로 D[n]=D[n−1]+D[n−2]+D[n−3]이다. 존재하지 않는 음수 인덱스는 더하지 않는다.

D[0]=1은 아무 수도 쓰지 않은 빈 합을 점화식을 시작하기 위한 한 가지 방법으로 세는 값이다. 문제에서 0을 입력받는다는 뜻은 아니다. 그러면 D[1]=1, D[2]=2, D[3]=4, D[4]=7이 된다. 4의 일곱 방법 중 1+3과 3+1은 순서가 달라 각각 세야 한다. 조합처럼 순서를 무시하면 이 답이 나오지 않는다.

코드는 i를 1부터 n까지 늘리며 마지막 수 j=1,2,3을 하나씩 시도한다. 각 상태에서 최대 세 값을 더하므로 시간 O(n), 배열 O(n) 공간이다. 입력에서 n<11이라 수치가 작지만, 범위가 훨씬 커지면 경우의 수 자료형이 넘치는지 먼저 확인해야 한다.

n	마지막 1	마지막 2	마지막 3	합계 D[n]
1	D[0]=1	0	0	1
2	D[1]=1	D[0]=1	0	2
3	D[2]=2	D[1]=1	D[0]=1	4
4	D[3]=4	D[2]=2	D[1]=1	7

코드의 바깥 반복이 목표 합 i이고 안쪽 반복이 마지막에 붙일 수 j다. 반복 순서를 뒤집어 숫자 1을 모두 처리한 뒤 2를 처리하면 동전 교환처럼 순서를 무시한 조합을 세는 풀이가 될 수 있다. 같은 1,2,3을 쓰더라도 무엇을 서로 다른 경우로 볼지에 따라 DP의 반복 순서가 달라진다.

소스코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- != 0) {
            int n = Integer.parseInt(in.readLine());
            out.write("" + plus123(n));
            out.write("\n");
        }
        out.flush();
        out.close();
        in.close();
    }
    public static int plus123(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3 && i - j >= 0; j++) {
                    dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
}