백준 15989번 - 1, 2, 3 더하기 4

문제

백준 15989번 - 1, 2, 3 더하기 4

아이디어

• "dp[n] = 1, 2, 3으로 n을 나타내는 방법의 수"라고 가정해서 시작했다가 순서가 다르면 같은 것으로 쳐야 하는 조건 때문에 도저히 일반화할 아이디어가 생각나지 않아 다른 점화식을 생각해봤다.
• "dp[i][n] = n을 1, 2, 3의 합으로 나타낼 때 마지막에 i를 더한 방법의 수"라고 가정한다. 그럼 i는 1,2,3이 될 수 있다.
• dp[1][n]은 마지막에 1을 더해서 n을 만드는 방법의 수이다. n-1에서 1을 더해 n을 만들어야 하므로 dp[1][n] = dp[1][n-1]과 같다.
• dp[2][n]은 마지막에 2를 더해서 n을 만드는 방법의 수이다. n-2에서 2를 더해 n을 만들어야 하므로 dp[2][n] = dp[1][n-2] + dp[2][n-2]와 같다.
• dp[3][n]은 마지막에 3을 더해서 n을 만드는 방법의 수이다. n-3에서 3을 더해 n을 만들어야 하므로 dp[3][n] = dp[1][n-3] + dp[2][n-3] + dp[3][n-3]과 같다.
• 1,2,3을 더하는 식을 수 오름차순으로 정리해놓고 보면 이해하기 좋다.
• 만약 순서가 다르면 다른 방법이라고 쳐야 했다면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]일 것이다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        int[][] dp = new int[4][10001];

        dp[1][1] = 1;

        dp[1][2] = 1;
        dp[2][2] = 1;

        dp[1][3] = 1;
        dp[2][3] = 1;
        dp[3][3] = 1;

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

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[1][n] + dp[2][n] + dp[3][n] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}