백준 9095번 : 1, 2, 3 더하기

백준 9095번 : 1, 2, 3 더하기

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

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int count = Integer.parseInt(br.readLine());
        int[] num = new int[11];
        num[1] = 1;
        num[2] = 2;
        num[3] = 4;
        for(int j = 4; j<=10; j++){
            num[j] = num[j-3] + num[j-2] + num[j-1];
        }
        for(int i = 0; i<count; i++){
            sb.append(num[Integer.parseInt(br.readLine())]).append("\n");
        }
        System.out.println(sb);
    }

    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

DP(Dynamic programming)의 맛을 처음 보았다. 작은 문제부터 해결해나가면서 점차 범위를 넓혀나가는 상향식 접근법으로 풀이 해야한다. DP문제는 결국 규칙을 찾아내는게 중요한 것 같다. 

 

풀이결론

 

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]  // n >= 4

 

숫자 4의 경우 1,2,3의 경우의 수의 합이 4의 경우의 수라는 규칙이 존재한다.

만약 숫자가 5라면, 2,3,4의 경우의 수의 합이 5의 경우의 수다. 

이 규칙을 활용해 점화식으로 풀면 된다.