백준 15990번: 1, 2, 3 더하기 5

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

백준 15990번: 1, 2, 3 더하기 5

문제풀이

위 문제는 1, 2, 3의 합으로 표현하는 모든 경우를 구하여야 합니다. 또한 같은 숫자를 연속해서 2번 이상 사용할 수 없습니다. 즉 마지막으로 사용한 숫자가 다시 연속으로 등장하면 안됩니다.

 

이 조건을 만족하기 위해 각 경우의 마지막으로 사용된 숫자를 명시적으로 관리해야 합니다.

 

이를 위해 2차원 배열을 사용해 dp[i][j]를 다음과 같이 정의합니다.

• dp[i][j]: i를 1, 2, 3의 합으로 나타날 때 마지막 숫자가 j인 경우의 수

🤔 왜 2차원 배열을 써야할까?

마지막으로 사용된 숫자를 추척함으로써, 같은 숫자가 연속해서 등장하지 않도록 관리할 수 있으며, 이를 통해 결과를 계산한다면 dp[i][1], dp[i][2], dp[i][3]의 값을 합하면 i를 만드는 모든 경우의 수를 구할 수 있기 때문입니다.

 

만약 dp[i]를 단순히 i를 만드는 모든 경우의 수로 정의한다면 마지막 숫자가 무엇인지 알 수 없습니다. 또한 점화식을 세울 때 중복된 계산이 발생하거나, 조건을 만족하는 않는 경우를 포함할 위험이 있습니다.

---

점화식 설명

2차원 배열 dp[i][j]는 위에서 "i를 1, 2, 3의 합으로 나타날 때 마지막 숫자가 j인 경우의 수"라고 정의했습니다.

수식의 마지막이 + 3 이라면 j는 1 or 2이 될 수 있습니다.

수식의 마지막이 + 2 이라면 j는 1 or 3이 될 수 있습니다.

수식의 마지막이 + 1 이라면 j는 2 or 3이 될 수 있습니다.

 

i를 7로 보고 1, 2, 3의 합을 나타낸다면 다음과 같이 볼 수 있습니다.

 

4 에서 3을 더해주고,

5 에서 2를 더해주고,

6 에서 1을 더해주면 각각 7이 됩니다.

 

7을 만들 수 있는 수식 중 3으로 끝나는 수식(마지막에 + 3인 경우)은

4를 만드는 수식에서 1(으)로 끝나는 것에 3을 더 하는 것

4를 만드는 수식에서 2(으)로 끝나는 것에 3을 더 하는 것

즉, dp[7][3] = dp[4][1] + dp[4][2] 입니다.

이를 점화식으로 표현하면 dp[n][3] = dp[n - 3][1] + dp[n - 3][2] 입니다.

 

7을 만들 수 있는 수식 중 2로 끝나는 수식(마지막에 + 2인 경우)은

5를 만드는 수식에서 1(으)로 끝나는 것에 2를 더 하는 것

5를 만드는 수식에서 3(으)로 끝나는 것에 2를 더 하는 것

즉, dp[7][2] = dp[5][1] + dp[5][3] 입니다.

이를 점화식으로 표현하면 dp[n][2] = dp[n - 2][1] + dp[n - 2][3] 입니다.

 

7을 만들 수 있는 수식 중 1로 끝나는 수식(마지막에 + 1인 경우)은

6을 만드는 수식에서 2(으)로 끝나는 것에 1을 더 하는 것

6을 만드는 수식에서 3(으)로 끝나는 것에 1을 더 하는 것

즉, dp[7][1] = dp[6][2] + dp[6][3] 입니다.

이를 점화식으로 표현하면 dp[n][1] = dp[n - 1][2] + dp[n - 1][3] 입니다.

 

이를 그림으로 표현한다면

 

7을 i로 즉, 점화식으로 설명한다면 다음과 같습니다.

 

마지막이 3으로 끝나는 경우 (dp[i][3])

• i - 3 에서 1로 끝나는 경우 3을 더함
• i - 3 에서 2으로 끝나는 경우 3을 더함
• dp[i][3] = (dp[i − 3][1]+dp[i − 3][2])

 

마지막이 2로 끝나는 경우 (dp[i][2])

• i - 2 에서 1로 끝나는 경우 2를 더함
• i - 2 에서 3으로 끝나는 경우 2를 더함
• dp[i][2] = (dp[i − 2][1]+dp[i − 2][3])

 

마지막이 1로 끝나는 경우 (dp[i][1])

• i - 1 에서 2로 끝나는 경우 1을 더함
• i - 1 에서 3으로 끝나는 경우 1을 더함
• dp[i][1] = (dp[i − 1][2]+dp[i − 1][3])

 

위와 같은 과정을 통해 n >= 4 일 때

dp[i][1] = dp[i - 1][2] + dp[i - 1][3]

dp[i][2] = dp[i - 2][1] + dp[i - 2][3]

dp[i][3] = dp[i - 3][1] + dp[i - 3][2] 라는 점화식이 나옵니다.

 

주어진 n에 대해 마지막으로 사용한 숫자가 다시 연속으로 등장하지 않도록 각자 마지막에 끝나는 숫자 1, 2, 3을 별도로 관리하여 합한 후, 마지막으로 dp[n][1], dp[n][2], dp[n][3]을 모두 더한 값이 정답이 됩니다.

 

dp[n][1] + dp[n][2] + dp[n][3]

문제에서는 1,000,000,009로 나눈 나머지를 출력하라고 되어 있기 때문에 코드는 다음과 같습니다.

 

🤔 1,000,000,009 으로 나눈 이유는?

n이 커질수록 가능한 경우의 수가 매우 커지게 됩니다. 이를 % 연산으로 적용된 dp[n]을 저장하지 않는다면 overflow가 발생할 수 있습니다. 따라서, 1,000,000,009로 나눈 나머지를 저장함으로써 결과의 안정성을 확보할 수 있습니다. 

코드

public class Main {

    private static final int MAX = 100_000;
    private static final int DIVISOR = 1_000_000_009;

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int t = Integer.parseInt(br.readLine());
            int[] arr = new int[t];
            for (int i = 0; i < t; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }
            for (long a : solution(t, arr)) {
                bw.write(a + "\n");
            }
            bw.flush();
        }
    }

    private static List<Long> solution(int n, int[] arr) {
        List<Long> list = new ArrayList<>();

        // dp[i][j]일 때 i가 4인 경우, j는 수식 마지막에 더하는 값
        // ex) i = 4, j = 1 or 2 or 3
        // dp[4][1] = (1+2+1, 3+1) = 경우의 수 2개
        // dp[4][2] = (x) = 경우의 수 0개
        // dp[4][3] = (1+3) = 경우의 수 1개
        // 총 경우의 수는 dp[4][1] + dp[4][2] + dp[4][3] = 3개
        long[][] dp = new long[MAX + 1][4];
        dp[1][1] = 1; // 1
        dp[2][2] = 1; // 2
        dp[3][1] = 1; // 1+2
        dp[3][2] = 1; // 2+1
        dp[3][3] = 1; // 3

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

        for (int i : arr) {
            long answer = (dp[i][1] + dp[i][2] + dp[i][3]) % DIVISOR;
            list.add(answer);
        }

        return list;
    }
}

public class Main {

    static long [][] dp = new long[100_001][4];
    static long mod = 1_000_000_009;

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int t = Integer.parseInt(br.readLine());
            int[] arr = new int[t];

            for (int i = 0; i < t; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }

            StringBuilder sb = new StringBuilder();
            dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
            int i = 4;

            for (int n : arr) {
                while (i <= n) {
                    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
                    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % mod;
                    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % mod;
                    i++;
                }
                long rs = (dp[n][1] + dp[n][2] + dp[n][3]) % mod;
                sb.append(rs).append("\n");
            }

            bw.write(sb.toString());
            bw.flush();
        }
    }
}