[Java] 백준 알고리즘 9095번 문제 (Dynamic Programming)

--- 문제 ---

백준 9095번 문제

--- 코드 ---

import java.util.Scanner;
public class Bj9095 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] n = new int[t];
        int max = 0;
        for(int i=0; i<t;i++) {
            n[i]=sc.nextInt();
            if(max<n[i]) max = n[i];
        }
        int dp[] = new int[max+1];
        dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=4;
        for(int i=4; i<=max;i++) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        for(int i=0; i<t;i++) {
            System.out.println(dp[n[i]]);
        }

    }}
     

동적계획법을 이용하였으므로, 이전 계산 값들은 배열에 저장되어 있으니까, 테스트 케이스 중 가장 큰 n 값까지의 갯수를 구하면 된다.

또한, 1,2,3 의 합으로 나타내는 방법의 수는

i가 4보다 큰 경우부터

dp[i] = dp[i-1]+dp[i-2]+dp[i-3]; 로 구할 수 있다.

 

 

--- 출처 ---

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