[Problem Solving] BOJ 15990: 1, 2, 3 더하기 5

문제 링크: https://www.acmicpc.net/problem/15990

 

n이라는 수가 1과 2와 3의 합으로 이루어 질 때, 더해지는 수가 연속적이지 않은 경우의 수를 구하는 문제이다.

 

dp테이블을 다음과 같이 정의할 수 있다.

dp[n][i]는 수의 합이 n일 때, 마지막으로 더해진 수가 i인 경우의 수이다.

따라서

dp[n][1] = dp[n - 1][2] + dp[n - 1][3] (1 + n - 1 = n)

dp[n][2] = dp[n - 2][1] + dp[n - 2][3] (2 + n - 2 = n)

dp[n][3] = dp[n - 3][1] + dp[n - 3][2] (3 + n - 3 = n)

라고할 수 있다.

 

결과로 dp[n][1] + dp[n][2] + dp[n][3] 를 출력하면 된다.

 

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

public class Main 
{
    public static int T;
    public static int n;
    public static long[][] dp;

    public static void input(BufferedReader br) throws IOException
    {
        n = Integer.parseInt(br.readLine());
    }

    public static void solution()
    {

    }

    public static void output()
    {
        System.out.println((dp[n][1] % 1000000009 + dp[n][2] % 1000000009 + dp[n][3] % 1000000009) % 1000000009);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Scanner sc = new Scanner(System.in);
        
        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] % 1000000009 + dp[i - 1][3] % 1000000009) % 1000000009;
            dp[i][2] = (dp[i - 2][1] % 1000000009 + dp[i - 2][3] % 1000000009) % 1000000009;
            dp[i][3] = (dp[i - 3][1] % 1000000009 + dp[i - 3][2] % 1000000009) % 1000000009;
        }

        T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++)
        {
            input(br);
            // input(sc);
            // solution();
            output();
        }
    }
}