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

문제 링크

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

문제 풀이

이전의 계산한 값들을 이용해서 그 다음 값을 구해야 하는 경우 dynamic programming으로 접근해야 한다는 생각이 들었다. 문제에서 n의 최대값이 11이라고 했기에 그것보다 하나 큰 12로 배열 크기를 잡았다.

dp[0]은 0으로 비워두고 dp[1] =1, dp[2] =2, dp[3] = 4가 나온다.
n이 1~3인경우에는 간단한 산수로 구해지는데 dp[4]의 경우에는 여러 경우의 수를 계산하면 7이 나온다.

i>=4에 대해서 다음 점화식이 성립한다.
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

코드

import java.util.*;


public class Main {

    static int[] dp = new int[12];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = dp[1] * dp[1] + 1;//2
        dp[3] = dp[1] * dp[2] + dp[2] * dp[1] + 1 - 1; //4

        // dp[4] = 7
        //dp[5] = 13

        for (int i = 4; i <= 11; i++) {
            dp[i] += dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            System.out.println(dp[num]);
        }
    }
}