[BOJ 5444] 시리얼 넘버

문제

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

5444번: 시리얼 넘버

 

---

알고리즘

• DP
• 슬라이딩 윈도우

---

풀이

각 테스트케이스마다 \(N\)개의 시리얼 넘버 \(S_{1} ... S_{N}\)과 \(M\)이 주어졌을 때 \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다:

 

• \(dp[i][j]:\) \(i\)번째 기타까지 고려했을 때 시리얼 넘버의 합을 \(M\)으로 나눈 나머지가 \(j\)가 되게 하는 기타의 최대 개수.

위와 같이 정의한다면, \(dp[i][j]\)에 \(i\)번째 기타의 시리얼 넘버, 즉 \(S_{i}\)를 포함시키는 경우와 포함시키지 않는 경우로 나눌 수 있습니다.

그러므로, \(k = (j + S_{i}) \text{ mod } M\)일 때, 다음과 같이 간단하게 점화식을 세울 수 있습니다:

$$dp[i][j] = max\begin{cases} dp[i][j]\\ dp[i - 1][j] \end{cases}$$

$$dp[i][k] = max\begin{cases} dp[i][k]\\ dp[i - 1][j] + 1 \end{cases}$$

하지만, \(1 \leq N \leq 500,\ 1 \leq M \leq 100000\)이므로 이렇게 하면, \(500 \cdot 100000 = 50000000\)으로 메모리 초과가 납니다.

위의 점화식을 보면 \(i\)에 대해서는 \(i\)와 \(i - 1\) 두 가지만 본다는 것을 알 수 있습니다.

그러므로, 슬라이딩 윈도우를 써서 메모리를 줄여줄 수 있습니다.

\(i\)를 \(\text{mod } 2\)로 두 수 \(0\)과 \(1\)로 나눠서 \(i\)를 둘 중에 하나, \(i - 1\)를 나머지 하나로 쓸 수 있습니다.

\(r = i \text{ mod } 2\)일 때, 점화식을 다음과 같이 고칠 수 있습니다:

$$dp[r][j] = max\begin{cases}dp[r][j]\\dp[\neg r][j]\end{cases}$$

$$dp[r][k] = max\begin{cases}dp[r][k]\\dp[\neg r][j] + 1\end{cases}$$

\(M\)의 배수라는 것은 \(M\)으로 나누었을 때 나머지가 \(0\)이므로 \(dp[N \text{ mod } 2][0]\)이 답이 됩니다.

 

(각 테스트케이스의) 시간복잡도: \(O(NM)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int N, M, arr[501], dp[2][100000]; cin >> N >> M;
        for (int i = 1; i <= N; ++i) cin >> arr[i];
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= N; ++i) {
            int n = i % 2;
            for (int j = 0; j < M; ++j) dp[n][j] = -1;
            for (int j = 0; j < M; ++j) {
                if (dp[!n][j] == -1) continue;
                int next = (j + arr[i]) % M;
                dp[n][j] = max(dp[n][j], dp[!n][j]);
                dp[n][next] = max(dp[n][next], dp[!n][j] + 1);
            }
        }
        cout << dp[N % 2][0] << '\n';
    }

    return 0;
}