[BOJ] 3037. 혼란 (🥇, DP/누적합)

🔗

풀이

N은 최대 1000이므로 모든 경우에 대해서 브루트 포스 방식으로 구하는 것은 1초 내에 연산이 불가능하다. 대신 규칙을 찾아보기로 했다.

간단하게 N=3에 대해 가능한 모든 경우의 수를 구하면 아래와 같다. 순서에 따라 정렬할 수 있는 가지수는 Nx(N-1)/2 = 6가지이다. 6가지 밖에 안 되기 때문에 직관적으로 바로 구할 수 있다.

이번에는 N=4에 대해 구해보았다.

우선 맨 앞의 숫자를 1로 고정하고 구하는 경우(왼쪽)과 맨 앞 숫자를 2로 고정하고 구하는 경우(오른쪽)로 나눠서 구했다. 맨 앞이 1로 고정된 경우 나머지 2,3,4에서 세 자리를 구하는 경우는 위에서 구한 N=3일 때와 동일하게 구할 수 있다. 숫자간의 차이값이 중요한 것이 아니라 크고 작음이 중요하기 때문이다.

맨앞이 2로 고정된 경우는 값이 달라지게 되는데 맨앞에 항상 2가 있고 뒤에는 항상 1이 있을 것이기 때문에 모든 경우의 수에 (2,1)짝이 추가되기 때문이다.

맨앞이 3, 4인 경우 역시 (3,2), (3,1)과 (4,2), (4,1), (4,3)이 추가된다. 맨 앞에 놓인 숫자가 나머지 숫자들 가운데 몇 번째로 큰 가에 따라 더해지는 숫자가 늘어나게 된다. 그림으로 정리하면 다음과 같다.

결국 dp[i][j]에 해당하는 값은 맨 앞의 숫자가 변경되는 횟수 만큼(k= 0 ~ N-1) dp[i-1][j-k] 값을 계속 더해주는 것이다. 그림에서 dp[4][3] 값을 구하면 아래와 같다.

dp[4][3] = dp[3][3] + dp[3][2] + dp[3][1] + dp[d][0]

❌ 시간 초과

하지만 점화식대로 구하니 시간 초과가 발생했다. 우선 3중 for문에서 O(N^2xM)로 사실상 이미 N^2에서 시간 초과가 발생할 수 밖에 없었다.

import java.util.*;
import java.io.*;

public class Main {
    static final int DIVIDE = 1_000_000_007;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int C = sc.nextInt();

        int[][] dp = new int[N+1][Math.min(C+1, (N*(N+1))/2 + 1)];
        dp[1][0] = 1;
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = 0; k < Math.min(C+1, (i * (i-1)) / 2); k++) {
                    if (k+j > C) continue;
                    dp[i][k+j] += dp[i-1][k];
                    dp[i][k+j] %= DIVIDE;
                }
            }
        }

        // for (int i = 0; i < dp.length; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }

        System.out.println(dp[N][C]);
    }
}

결국 점화식을 재정리해서 풀 수 밖에 없었다. 해당 점화식을 풀어 써보면 아래와 같이 중복되는 부분들이 있는 것을 알 수 있다.

dp[5][6]를 dp[5][5]와 연관지어서 정리할 수 있을 것 같다.

dp[5][6] = dp[4][6] + dp[5][5] - dp[4][1]

이때 dp[5][5]에 있는 dp[4][1] 값을 무엇으로 정의해야 하는지가 문제이다. 나머지는 단순히 N-1 또는 C-1을 하면 되는 값이지만 N과 C를 사용해서 dp[4][1]을 정의하려면 어떻게 해야할까를 고민했다.

그런데 k=0부터 N-1까지 더하는 것이라고 했으므로 C-K의 값은 차례대로 5, 4, 3, 2, 1이 될 것이고 결국 dp[4][1]에서 1의 값은 K가 N-1(4)일 때의 C-K값이라고 정의할 수 있다. 여기서는 dp[5][5]기준이기 때문에 C=5이지만 dp[5][6]에 해당 값을 대입하기 위해서는 C=6을 기준으로 계산해야 한다.

dp[4][1] = dp[N-1][C-N]으로 정의할 수 있다

결국 정리하면 진짜 점화식은 다음과 같다.

dp[N][C] = dp[N-1][C] + dp[N][C-1] - dp[N-1][C-N]

📌 주의 사항

1️⃣ 메모리 초과

이때 배열을 전부 만들어서 사용하게 되면 최대 배열의 크기가 1000x10000라서 메모리 초과가 발생한다. 어차피 N행과 N-1행 2개의 행만 사용하기 때문에 dp를 2개의 행으로 만들어서 번갈아 사용하는 방식을 쓰면 최대 배열의 크기가 2만으로 메모리 초과가 발생하지 않을 수 있다.

2️⃣ 음수를 MOD로 나눴을 때 나머지

dp[i%2][j] = (dp[i%2][j-1] + dp[1-i%2][j] - (j >= i ? dp[1-i%2][j-i] : 0) + MOD) % MOD;

해당 값을 계산할 때 MOD의 동작 방식은 다음과 같다.

(A+B-C)%MOD = (A%MOD) + (B%MOD) - (C%MOD)

모든 연산의 순간에 대해 (A+B)는 항상 C보다 크지만 MOD로 나눠진 나머지 값은 C보다 작아질 수 있다. 결국 중간에 음수가 발생할 수 있는 것이다. 그렇기 때문에 제대로 된 결과값을 얻기 위해서는 항상 나머지가 양수가 나올 수 있도록 보장해야 한다. 이를 보장하기 위해 음수가 나올 경우를 대비해 MOD값을 한 번 더한 후 나눠주게 된다.

✅ 통과 코드

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1_000_000_007;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int C = sc.nextInt();

        long[][] dp = new long[2][C+1];
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            dp[i%2][0] = 1;
            for (int j = 1; j <= C; j++) {
                dp[i%2][j] = (dp[i%2][j-1] + dp[1-i%2][j] - (j >= i ? dp[1-i%2][j-i] : 0) + MOD) % MOD;
                // dp[i%2][j] %= MOD;
            }
        }
        System.out.println(dp[N%2][C]);
    }
}

---

참고

• https://kth990303.tistory.com/60
• https://hellojaehoon.tistory.com/71