DP - 9095(1, 2, 3 더하기)

9095번 제출 (acmicpc.net)

로그인

적절한 점화식을 찾는것이 중요합니다. 1,2,3만을 통해서 합을 나타내는 수를 출력해야하므로 4에 대한 합을 찾는다 가정하였을때 

4일 경우 경우의 수는 

 

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

즉, 7 = 4 + 2 + 1 -> f(4) = f(3) + f(2) + f(1)다음과 같이 바꿀 수 있습니다. 

 

5일 경우까지 해본다면, 

 

• 1+1+1+1+1
• 2+1+1+1
• 1+2+1+1
• 1+1+2+1
• 1+1+1+2
• 2+2+1
• 2+1+2
• 1+2+2
• 3+1+1
• 1+3+1
• 1+1+3
• 3+2
• 2+3

총 13가지가 나오고 

 

13 = 7 + 4 +2 -> f(5) = f(4) + f(3) + f(2)라는 결과가 나옵니다.

 

점화식으로는  f(n) = f(n-1) + f(n-2) + f(n-1)으로 나타 낼 수 있습니다. 이를 재귀방식으로 코드를 짠다면,

package com.company;

import java.util.Scanner;




public class Main {
    static int result[] = new int[1001];

    public static int cal(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        result[3] = 4;

        if(result[n] != 0 ){
            return  result[n];
        }
        else {
            result[n] = (cal(n - 1) + cal(n - 2) + cal(n-3)) % 10007;
        }

        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i<n; i++){
            int num = sc.nextInt();
            System.out.println(cal(num));
        }


    }
}

다음과 같은 코드를 만들 수 있습니다.