[백준] 9095 1, 2, 3 더하기 자바(Java)

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

9095번: 1, 2, 3 더하기

 

문제 :  n을 1, 2, 3의 합으로 나타내는 방법의 수

 

접근.

countSum( 1 ) =  1

countSum( 2 ) =  2

countSum( 3 ) =  4

countSum( 4 ) =  7

countSum( 5 ) =  13

...

n = 5까지 단순하게 숫자를 세본 결과 규칙을 찾을 수 있었다.
countSum( n ) = countSum( n - 1) + countSum( n - 2) + countSum( n - 3)

 

증명.

n = 4일 때

맨 마지막 더하기 값에는 3가지 값이 들어갈 수 있다.

1, 2, 3 (문제에서 1, 2, 3 만 사용하게 제한)

 

 

마지막 값이 1인 경우 :

앞에 값에 올 수 있는 경우의 수는 countSum( 3 ) + 1

마지막 값이 2인 경우 : 

앞에 값에 올 수 있는 경우의 수는 countSum( 2 ) + 2

마지막 값이 3인 경우 :

앞에 값에 올 수 있는 경우의 수는 countSum( 1 ) + 3

 

그래서 n = 4일 때 나타내는 방법은 이 세 가지의 경우의 수의 총합이 된다.

 

 

n = 5일 때

마지막 값이 1인 경우 :

앞에 값에 올 수 있는 경우의 수는 countSum( 4 ) + 1

마지막 값이 2인 경우 : 

앞에 값에 올 수 있는 경우의 수는 countSum( 3 ) + 2

마지막 값이 3인 경우 :

앞에 값에 올 수 있는 경우의 수는 countSum( 2 ) + 3

 

그래서 n = 5일 때 나타내는 방법은 이 세 가지의 경우의 수의 총합이 된다.

 

 

자바 코드

package main;

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

public class Main {

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int input = Integer.parseInt(bf.readLine());

        int[] dp = new int[12];

        for (int i = 0; i < input; i++) {
            int n = Integer.parseInt(bf.readLine());

            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;

            for (int j = 3; j <= n; j++) {
                dp[j] = dp[j-1] + dp[j-2 ] + dp[j-3];
            }

            System.out.println(dp[n]);
        }
    }

}
        

이해되지 않는 부분이 있으면 질문 남겨주세요!