[백준] 9095: 1,2,3 더하기

문제

문제 풀이

n=1부터 n=4까지 작성해보니 다음과 같은 규칙을 찾았다.

즉, 규칙은 다음과 같다.
f(n) = f(n-3) + f(n-2) + f(n-1)

n번째 숫자는 다음의 경우를 더한 경우의 수로 연산할 수 있다.

• n-3번째 연산 조합에서 3을 더한 경우
• n-2번째 연산 조합에서 2을 더한 경우
• n-1번쨰 연산 조합에서 1을 더한 경우

코드

import java.util.Scanner;

public class ANS9095 {
    static Integer[] dp;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        dp= new Integer[14];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i = 0 ; i < num ; i++){
            int element = sc.nextInt();
            System.out.println(recur(element));
        }

    }

    static int recur(int N){
        if(dp[N] == null){
            for(int i = 4 ; i < N+1  ; i++){
                dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
            }
        }

        return dp[N];
    }
}