[백준] 9095번 1, 2, 3 더하기(JAVA)

문제

- 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수 구하기

- n은 양수, 11보다 작음

- 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지(1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)

 

해결방법

1, 2, 3으로 조합해서 경우의 수를 구하는 것이기 때문에 1, 2, 3을 만들 수 있는 방법을 먼저 생각해보았다. 

1은 1 밖에 없으므로 경우의 수 1이다. (dp[1] = 1)

2는 1+1, 2 이므로 경우의 수 2이다. (dp[2] = 2)

3은 1+1+1, 1+2, 2+1, 3 이므로 경우의 수는 4이다. (dp[3] = 4)

 

4는 1+3, 2+2, 3+1로 나타낼 수 있다.

1. 1+3일 때, 3을 만드는 경우의 수는 4이다.

2. 2+2일때, 2를 만드는 경우의 수는 2이다.

3. 3+1일때, 1을 만드는 경우의 수는 1이다.

따라서, 4는 4+2+1 = 7가지의 경우의 수가 있다. (dp[4] = 7)

 

5는 1+4, 2+3, 3+2로 나타낼 수 있다.

1. 1+4일때, 4를 만드는 경우의 수는 7이다.

2. 2+3일때, 3을 만드는 경우의 수는 4이다.

3. 3+2일때, 2를 만드는 경우의 수는 2이다.

따라서, 5는 7+4+2 = 13가지의 경우의 수가 있다. (dp[5] = 13)

 

다음과 같은 규칙에 따라서 해당 정수 n의 경우의 수를 구하고 싶을 때, n-1, n-2, n-3번째의 경우의 수를 더해주면 구할 수 있다.

 

코드

import java.io.*;

public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int[] dp = new int[11];			// n이 11보다 작으므로 11로 크기 지정 후 시작

        dp[1] = 1;					// (1)
        dp[2] = 2;					// (1+1), (2)
        dp[3] = 4;					// (1+1+1), (1+2), (2+1), (3) 

	// 4부터 10까지 경우의 수 구하기
        for(int i = 4; i<11; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        for(int tc=1; tc<=T; tc++){
            int n = Integer.parseInt(br.readLine());
			
            // 입력 받은 정수의 경우의 수 출력
            int result = dp[n];

            sb.append(result+"\n");
        }
        System.out.println(sb);
    }
}