[백준] 1,2,3 더하기 - 9095

링크

https://www.acmicpc.net/problem/9095

문제

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

풀이

DP를 이용해 풀었다. 길이가 12인 정수형 배열에 패턴을 이용해 찾은 값을 저장했다.
패턴을 아래와 같다.

F(n)이 n을 1,2,3의 합으로 나타내는 방법의 수를 반환하는 함수라 했을 때,
F(n) = F(n-1) + F(n-2) + f(n-3)이 성립한다.(n>3)

즉, 1, 2, 3은 미리 채워두고 배열을 순회하며 값을 채우면 된다.

입력 받은 T개의 n 중 가장 큰 값까지만 배열을 순회하면 되지만, 문제의 조건 중 n의 최댓값이 11이므로
배열을 미리 11까지 채운 뒤에 입력을 받도록 했다.

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        
        // Array[int] | 0~11 저장, 각 수 마다 테스트 케이스 저장
        int[] arr = new int[12];
        arr[1] = 1; // 1
        arr[2] = 2; // 1+arr[1]: 1+1, 
                    // 2+arr[0]: 2+0
        arr[3] = 4; // 1+arr[2]: 1+1+1, 1+2
                    // 2+arr[1]: 2+1
                    // 3+arr[0]: 3+0
        // 4 | 1+arr[3]: 1+3, 1+1+1+1, 1+1+2, 1+2+1
        // 4 | 2+arr[2]: 2+2, 2+1+1
        // 4 | 3+arr[1]: 3+1
        // 5 | 1+arr[4]: 1+1+3, 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+2, 1+2+1+1, 1+3+1
        // 5 | 2+arr[3]: 2+1+1+1, 2+1+2, 2+2+1, 2+3
        // 5 | 3+arr[2]: 3+1+1, 3+2

        for(int i=4; i<12; i++){
            arr[i] =  arr[i-1] + arr[i-2] + arr[i-3]; 
        }

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(arr[n] + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}