[BOJ] 15988. 1, 2, 3 더하기 3 (🥈, DP)

풀이

아이디어

1, 2, 3 세 가지 숫자를 사용해서 더할 수 있는 방법의 개수에 대해 구하는 문제이다. n의 최대 값은 백만으로 모든 경우의 수를 dfs로 구한다는 건 불가능했다. 이미 구해진 값으로부터 누적해서 구해나가는 다이나믹 프로그래밍 방법으로 접근했다.

우선 1을 구하는 방법은 1 딱 한 가지다.
하지만 2를 구하는 방법은 2 한 가지에, 1에다가 1을 더 하는 방법 총 2가지이다.
3을 구하는 방법은 마찬가지로 3 한 가지에, 2에다가 1을 더하는 방법이 있을 것이다. 그런데 수는 1, 2, 3 세 가지를 사용할 수 있다고 했으므로 이번에는 1 에다가 2를 더하는 방법도 있을 것이다.

그리고 여기에 추가적으로 1+1에 1을 더하는 방법도 있다.

1+1이 어디에서 나왔냐 하면 2를 구하는 방법에서 나온 것이다. 즉 3을 구하는 방법은 다음 세 가지로 분류할 수 있다.

1. 3을 구하는 방법 (3 그 자체)
2. 1을 구하는 방법 (1에다가 2를 더하면 되므로)
3. 2을 구하는 방법 (2에다가 1을 더하면 되므로)

그림으로 나타내면 파란색 형광펜으로 칠한 부분이 2를 구하는 방법들이다. 3의 경우 2에서 1을 더하면 되고, 4는 2에다가 2를 더한다는 차이만 있을 뿐이다.

이건 3을 구하는 방법에도 적용될 수 있다. 4는 3에다가 1만 더하면 된다. 결국 4를 구하는 방법은 아래와 같이 3가지다

1. 3을 구하는 방법 (3 에다가 1을 더하면 되므로)
2. 1을 구하는 방법 (1에다가 3를 더하면 되므로)
3. 2을 구하는 방법 (2에다가 2을 더하면 되므로)

현재 수가 n일 때 n-1, n-2, n-3수를 1,2,3 으로 만드는 방법의 수를 모두 더하면 되는 것이다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] (i >= 4)

코드

n의 최대값이 백만이기 때문에 경우의 수를 구할 경우 10억을 넘어가게 된다. 한 번 값을 구할 때마다 제시된 수로 나눠주지 않으면 사용하는 자료형의 최대값을 넘어서 잘못된 값이 구해질 가능성이 있다.(오버플로우)

자바에서는 오버플로우되면서 잘못된 값이 도출되어 틀렸습니다가 뜨지만 파이썬의 경우는 메모리 초과로 에러가 발생한다.

그리고 각 테스트 케이스마다 매번 n에 대한 값을 구하려고 하면 이번에는 시간 초과가 발생한다. 풀이 자체가 누적을 통해 구하는 것이므로 만약 첫 번째 값이 100만이었다면 그 뒤에 구하게 될 값들은 첫 번째 값을 구할 때 이미 다 구해진 값들일 것이다. 그냥 처음부터 백만짜리 배열을 만들어놓고 모든 경우의 수에 대해 구한 후 각 테케에서 주어지는 n에 대해 해당하는 값을 출력하는 방식으로 풀이하면 해결할 수 있다.

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

public class Main {
    public final static int DP_LENGTH = 1_000_001;
    public final static int DIVIDE_NUMBER = 1_000_000_009;
    public static long[] dp = new long[DP_LENGTH+3];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        memo();

        while (T > 0) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n] % DIVIDE_NUMBER);
            T--;
        }
    }

    public static void memo() {

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

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