[Java] 다이나믹 프로그래밍 (1,2,3 더하기 4)

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

15989번: 1, 2, 3 더하기 4

 

다이나믹 프로그래밍으로 점화식을 구해서 풀어야 하는 문제.

1차원 적으로 생각했다가 도저히 답이 안 나왔는데 dp 테이블을 2차원 배열로 나누어 풀어야지 풀 수 있었다.

 

dp[i][0] : i를 만들 때 1이 가장 앞에 오는 경우 ex) i=4 1+1+1+1

dp[i][1] : i를 만들 때 2가 가장 앞에 오는 경우 ex) 2+1, 2+2

dp[i][2] : i를 만들 때 3이 가장 앞에 오는 경우 ex) 3+1

 

위처럼 2차원으로 3가지 경우로 나누어서 생각해야 함.

 

점화식

• dp[i][0] = 1                                                      맨 앞에 1이 오는 경우는 오직 1의 합으로 표현하는 경우 하나밖에 없다.
• dp[i][1] = dp[i-2][0] + dp[i-2][1]                    맨 앞에 2가 오는 경우는 뒤에 3은 올 수 없으므로 제외하고 이미 2를 앞에 썼기 때문에 i에서 2를 뺀 수의 맨 앞에 1이 오는 경우, 2가 오는 경우를 더해주어야 한다.
• dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2]  맨 앞에 3이 오는 경우는 이미 3을 앞에 썼기 때문에 i에서 3을 뺀 수의 맨 앞에 1,2,3이 오는 경우를 더해 준다.

 

위 점화식은 N>=4 일 때 기능한다. 따라서 N <4 일 때의 경우를 수기로 작성해 주자.

 

 

 

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb =new StringBuilder();

        int T, number;
        int[][] dp = new int[10001][3];

        dp[1][0] = 1; //1로 시작해 1을 표현하는 방법 1
        dp[2][0] = dp[2][1] = 1; //각각 1과 2로 시작해 2를 표현하는 방법 1+1, 2
        dp[3][0] = dp[3][1] = dp[3][2] = 1; //각각 1,2,3으로 시작해 3을 표현하는 방법 1+1+1, 2+1, 3

        for(int i=4; i<10001; i++){
            dp[i][0] = 1;
            dp[i][1] = dp[i-2][0] + dp[i-2][1];
            dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2];
        }

        T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++){

            number = Integer.parseInt(br.readLine());

            sb.append(dp[number][0]+dp[number][1]+dp[number][2]+"\n");

        }
        System.out.println(sb);
    }
}