[알고리즘][DP][9095] 1, 2, 3 더하기

[알고리즘][DP][9095] 1, 2, 3 더하기

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

[풀이]

• DP에서 가장 중요한 것은 점화식 찾기!
• 경우의 수를 모두 구하려 하지말고 규칙을 찾아 반복해줘야 한다.
• 당연한 것들을 이용해서 규칙을 찾자
• D[n] 은 1, 2, 3으로 이루어지는 방법의 수 

? + ? + ? + …… + ? + ? = n 라고 하자.

n 이 되려면 3가지 방법이 있다.

• ? + ? + ? + …… + ? + 1 = n 일 경우  
• ? + ? + ? + …… + ? = n-1 이다.
• ? + ? + ? + …… + ? + 2 = n 일 경우  
• ? + ? + ? + …… + ? = n-2 이다.
• ? + ? + ? + …… + ? + 3 = n 일 경우  
• ? + ? + ? + …… + ? = n-3 이다.

• n-1, n-2, n-3 역시 각각 구성되는 방법의 수를 D[n-1], D[n-2], D[n-3]이라고 하자.
• 즉, 점화식은 D[n] = D[n-1] + D[n-2] + D[n-3] 

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class q_9095 {
    
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int test_num = scan.nextInt();
        while(test_num!=0) {
            test_num--;
            int num = scan.nextInt();
            System.out.println(DP(num));
        }
        
    }
    
    public static int DP(int num) {
        int[] D = new int[1001];
        D[0]=1;
        D[1]=1;
        D[2]=2;
        for(int i=3;i<=num;i++) {
            D[i] = D[i-1] + D[i-2] + D[i-3];
        }
        
        return D[num];
    }
}