[백준] 9095 1, 2, 3 더하기(Silver.3) - DP(동적 계획법)

문제

문제 해설

1~5일 때 방법의 수를 모두 그려보았다.

모든 경우의 수를 구해보니 n이 3보다 클 때, n의 방법의 수는 n-1, n-2, n-3의 방법의 수를 모두 더한 값임을 알 수 있었다. 예를 들어, n이 5일 때는 4일 때 방법의 수 + 3일 때 방법의 수 + 2일 때 방법의 수를 더한 값이 된다. 즉, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이라는 공식을 도출할 수 있다. 따라서 상향식(Bottom-up) 접근법을 통해 이를 구현해보았다.

package DP;

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

public class _9095_1_2_3_더하기 {
    public static void main(String[] arge) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int[] memo = new int[11];
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 4;
        for (int i = 4; i <= 10; i++) {
            memo[i] = memo[i-3] + memo[i-2] + memo[i-1];
        }

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            System.out.println(memo[Integer.parseInt(br.readLine())]);
        }
    }
}