[BOJ] 1, 2, 3 더하기 5

DP를 이용한 문제이다.

이 문제의 기본 점화식은 다음과 같다.

dp[n]= dp[n-1] (1을 더해주는 경우) + dp[n-2] (2를 더해주는 경우) + dp[n-3] (3을 더해주는 경우) , 하지만 이 문제에서는 연속하여 두개이상의 자연수를 사용하면 안되는 조건이 생겼기에 다음과 같이 dp배열을 설계하였다.

dp[n][i] => i의 숫자를 맨마지막 숫자로 가지는 경우
예를 들면 n=3일 경우 dp[3][1]은 2+1 이 있으므로 1, dp[3][2]은 1+2 이 있으므로 1, dp[3][3]은 3이 있으므로 1이 나오게 된다. 이런식으로 최종 점화식을 구하면

dp[n][1] = dp[n-1][2] + dp[n-1][3], 1을 더하는 경우 n-1에서 2와 3으로 끝나는 것에 더할 수 있음.
dp[n][2] = dp[n-2][1] + dp[n-2][3], 2를 더하는 경우 n-2에서 1와 3으로 끝나는 것에 더할 수 있음.
dp[n][3] = dp[n-3][1] + dp[n-3][2], 3을 더하는 경우 n-3에서 1와 2으로 끝나는 것에 더할 수 있음.

위와 같이 풀 수 있다.

package boj.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_15990_123더하기5 {
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        
        long[][] dp=new long[100001][4];
        dp[1][1]=1; dp[1][2]=0; dp[1][3]=0;
        dp[2][1]=0; dp[2][2]=1; dp[2][3]=0;
        dp[3][1]=1; dp[3][2]=1; dp[3][3]=1;
        
        for(int i=4;i<=100000;i++) {
            dp[i][1]=dp[i-1][2]+dp[i-1][3]; dp[i][1]=dp[i][1]%1000000009;
            dp[i][2]=dp[i-2][1]+dp[i-2][3]; dp[i][2]=dp[i][2]%1000000009;
            dp[i][3]=dp[i-3][1]+dp[i-3][2]; dp[i][3]=dp[i][3]%1000000009;
        }
        
        int T=Integer.parseInt(br.readLine());
        for(int tc=1;tc<=T;tc++) {
            int N=Integer.parseInt(br.readLine());
            System.out.println((dp[N][1]+dp[N][2]+dp[N][3])%1000000009);
            
            
        }
        
        
        
    }
}