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

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

9095번: 1, 2, 3 더하기

 

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

public class Main{
    public static int[] dp = new int[11];
    public static int solution(int n){
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<=n; i++){
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while(T-->0){
            int n = Integer.parseInt(br.readLine());
            System.out.println(solution(n));
        }
    }
}

 

dp[1] = 1

dp[2] = 1+1, 2

dp[3] = 1+1+1, 1+2, 2+1, 3 

 

으로 표현할 수 있으므로 배열에 dp[1] =1, dp[2]=2. dp[3]=4를 저장한다.

4는 1+3, 2+2, 3+1로 표현할 수 있는데 이는

각각

1+dp[3] :4가지 

2+dp[2] :2가지

3+dp[1] :1가지

 

와 같으므로 7가지이다.

 

마찬가지로 5는 다음과 같이 총 13가지가 나온다.

 

1+4 = 1+dp[4] :7가지

2+3 = 2+dp[3] :4가지

3+2 = 3+dp[2] :2가지

 

이를 통해 점화식을 세우면 dp[n] = dp[n-3]+dp[n-2]+dp[n-1] (n>=3) 이 된다.

 

 

이 문제를 처음에 제출했을 때 dp배열의 크기를 n+1로 잡았었는데, ArrayIndexOutOfBounds 런타임 에러가 떴다.

그 이유는 입력으로 들어오는 수가 3보다 작은 경우 배열의 크기에 넘어서는 인덱스에 값을 대입하려해서이다.

그러므로 문제에서 제시한 범위대로 배열의 크기를 11로 바꿔줬다.