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

 

문제

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구해라.

 

 

풀이

1) 1을 1,2,3의 합으로 나타내는 방법 [1 단독으로 사용가능]
- 1가지 : (1)

- 1 단독
2) 2을 1,2,3의 합으로 나타내는 방법 [2 단독으로 사용가능]

- 2가지 : (1,1) / (2) 

- [1]을 만드는 경우에 1을 합한 경우 / 2 단독

3) 3을 1,2,3의 합으로 나타내는 방법 [3 단독으로 사용가능]
- 4가지 : (1,2)/ (1,1,1) (2,1) / (3)

- [1]을 만드는 경우에 2를 합한 경우 / [2]를 만드는 경우에 1을 합한 경우 / 3 단독

4) 4를 1,2,3의 합으로 나타내는 방법 [단독으로 사용가능한 숫자없음]
- 7가지 : (1,3) / (1,1,2) (2,2) / (1,1,1,1) (1,2,1) (2,1,1) (3,1)

- [1]을 만드는 경우에 3을 합한 경우 / [2]를 만드는 경우에 2를 합한 경우 / [3]을 만드는 경우에 1을 합한 경우

5) 5를 1,2,3의 합으로 나타내는 방법 [단독으로 사용가능한 숫자없음]
- 13가지 : (1,1,3) (2,3)  / (1,2,2) (1,1,1,2) (2,1,2) (3,2) / (1,3,1) (1,1,2,1) (2,2,1) (1,1,1,1,1) (1,2,1,1) (2,1,1,1) (3,1,1)

- [2]을 만드는 경우에 3을 합한 경우 / [3]를 만드는 경우에 2를 합한 경우 / [4]을 만드는 경우에 1을 합한 경우

.....

 

따라서 단독으로 사용가능한 숫자가 있는 1,2,3의 경우는 이전 시행의 경우 + 1(자기자신 단독 사용)

단독으로 사용한 숫자가 없는 숫자들은 이전 시행 + 전전 시행 + 전전전 시행의 경우를 더해준다.

 

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for (int i = 4; i < 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            sb.append(dp[Integer.parseInt(br.readLine())]).append("\n");
        }
        System.out.println(sb);
    }
}