알고리즘 풀이 - 백준 15988(1, 2, 3 더하기 3, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
관련 문제인 9095번(1, 2, 3 더하기) 포스팅은 여기를 참조
관련 문제인 15990번(1, 2, 3 더하기 5) 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

 

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제

 

 

2. 풀이

 

이 문제는 상단에 표기한 9095번과 같은데 정수 n의 범위가 넓어졌고 그 결과를 특정 수로 나누어야 한다는 것에 차이가 있다.

 

간단하게 푸는 방법은 9095와 같으니 다시 한 번 아래와 같이 참고하자.

 

정수 n을 1, 2, 3의 합으로 나타내는 방법은 아래와 같다.

n = (n-3) + 3
n = (n-2) + 2
n = (n-1) + 1

즉, 작은 문제들인 n-3, n-2, n-1을 반복하여 사용하고 해당 최적 결과값이 그대로 사용되므로 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 아래와 같을 것이다.
정의 : dp[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수

n 하나 만이 변수이므로 1차원의 배열을 통해 상태 저장이 가능할 것이다. 기저 상태와 점화식을 세워보자.

기저 상태는 n이 1, 2, 3의 경우일 것이다. n=1일 때는 1로 한 가지만 가능하며, 2는 1+1과 2의 2가지, 3은 1+1+1, 1+2, 2+1, 3의 4가지이다.
기저 상태 : dp[1] = 1, dp[2] = 2, dp[3] = 4

점화식은 아래와 같다.
점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] dp;
    static final int MOD = 1000000009;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 최대 1,000,000까지 나오므로 미리 저장
        dp = new int[1000001];
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            for(int j=4; j <= n; j++){
                dp[j] = ((dp[j-3] + dp[j-2]) % MOD + dp[j-1]) % MOD;
            }
            bw.write(dp[n] + "\n");
        }
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] dp;
    static final int MOD = 1000000009;
    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());
        dp = new int[1000001];
        // 기저 상태는 1, 2, 3을 나타내는 방법의 수
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for(int i=0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(topDown(n)) + "\n");
        }
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n){
        if(dp[n] > 0) return dp[n];
        return dp[n] = ((topDown(n-1) + topDown(n-2)) % MOD + topDown(n-3)) % MOD;
    }
}

참고로 Top-Down을 쓸 때는, topDown(n-1) + topDown(n-2) + topDown(n-3)으로 하면 시간초과 없지만 반대로 쓰면 시간 초과가 난다.

아마도 n-1은 하나씩 건너뛰며 모든 경우의 수를 미리 다 채워넣으면서 돌아오지만 n-3은 3개씩 건너뛰면서 돌아와서 채워지지 않는 부분이 있어 그 뒤에 있는 n-2를 추가로 재귀로 더 호출하며 호출 횟수가 기하급수적으로 증가하기 때문으로 추측된다.

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.