BOJ 백준 5444번 시리얼 넘버

​​

 

BOJ 백준 5444 시리얼 넘버

 

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

 

N개의 기타가 존재하고, 이 중에는 강토가 갖고 있는 기타가 있다. 강토가 소유하는 기타의 시리얼 넘버를 모두 합한 값은 M의 배수이다. N개의 모든 기타의 시리얼 넘버와 M이 주어졌을 때, 가능한 강토의 기타 개수의 최댓값을 구해야 한다.

 

다음과 같은 배열을 정의하면 동적 프로그래밍(Dynamic Programming)으로 해결 가능하다.

 

dp[i][j]: i번째 기타까지 봤고, 이 중에서 강토가 갖고 있는 기타의 시리얼 넘버 합을 M으로 나누었을 때의 값이 j일 때의 가능한 강토의 기타 개수의 최댓값

 

아래는 풀이 과정을 정리한 것이다.

 

---

1) 우선 dp 배열 값을 모두 -1로 초기화한다.

2) N개의 기타를 첫 번째 기타부터 N 번째 기타까지 차례대로 보면서 dp 배열 원소 값을 구해 내간다.

    (1) i번째 기타를 강토의 것에 포함시키지 않는 경우 ⇔ dp[i][j] < dp[i - 1][j]인 경우

        dp[i][j] = dp[i - 1][j]

    (2) i번째 기타를 강토의 것에 포함시키는 경우 ⇔ dp[i][(j + s[i]) % m] < dp[i - 1][j] + 1

        dp[i][(j + s[i]) % m] = dp[i - 1][j] + 1

---

 

그런데 N의 최댓값이 500이고 M의 최댓값은 100,000이어서 dp[N][M] 배열을 선언하면 메모리 초과가 발생한다. 모든 N개의 기타를 첫 번째부터 N 번째 기타까지 차례대로 dp 원소 값을 구해 나가는데, 매번 값을 구하는 단계에서 모든 배열의 값이 필요한 것은 아니다. i 번째 기타를 볼 때 i - 1 번째 기타까지 봤을 때의 dp 값만 필요하므로 dp의 메모리 크기를 줄일 수 있고, 이는 슬라이딩 윈도우(Sliding Window) 기법의 일종이다. 따라서 dp[2][M] 배열만 선언해도 구할 수 있다.

 

 

이를 종합하여 코드를 구현하면 아래와 같다.

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;


const int N_MAX = 500;
const int M_MAX = 100000;


int t, n, m;


int s[N_MAX + 1];
int dp[2][M_MAX]; // 슬라이딩 윈도우


int main(){
    scanf("%d", &t);
    while(t--){
        memset(dp, -1, sizeof(dp));
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++){
            scanf("%d", &s[i]);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 0; j < m; j++){
                dp[1][j] = -1;
            }
            
            for (int j = 0; j < m; j++){
                if (dp[0][j] == -1) continue;
                if (dp[1][j] == -1 || dp[1][j] < dp[0][j]) {
                    dp[1][j] = dp[0][j];
                }
                int next = (j + s[i]) % m;
                if (dp[1][next] == -1 || dp[1][next] < dp[0][j] + 1) {
                    dp[1][next] = dp[0][j] + 1;
                }
            }
            
            for (int j = 0; j < m; j++){
                dp[0][j] = dp[1][j];
            }
        }
        
        printf("%d\n", dp[0][0]);
    }
    
    
    return 0;
}