SUSHI (중, p. 355)

문제#

어떻게 풀었나?#

슬라이딩 윈도우 기법을 적용하여 풀었다.

m이 21억정도 되는데, price로 들어오는 값이 100의 배수이므로 일단 100으로 나누고 시작했다. 그러면 2100만정도 되는 값이고, 배열에 담을 수 있는 적당한 개수만 dp배열로 만들어서 상태공간을 구성했다. 최대 가격이 2만인데, 100으로 나누면 200이므로, 상태공간은 dp[2][201] 이상만 되면 된다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int price[21], like[21];
int dp[2][20001];
int n;
const int GIJUN = 20000;
int main() { 
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        ll m;
        cin >> n >> m;
        m/=100;
        memset(dp,0,sizeof(dp));
        for(int i=0; i<n; i++) {
            cin >> price[i] >> like[i];
            price[i]/=100;
        }
        int i,t=0,j=0;
        for(i=0; i<=m; i++,j++) {
            for(int k=0; k<n; k++) {
                if(j-price[k]>=0) {
                    dp[t][j] = max(dp[t][j], dp[t][j - price[k]] + like[k]);
                }
            }
            if(j==GIJUN-1) break;
        }
        if(j==GIJUN-1) {
            i++;
            t ^= 1;
            j=0;
        }
        for(; i<=m; i++,j++) {
            for(int k=0; k<n; k++) {
                if(j-price[k]>=0) {
                    dp[t][j] = max(dp[t][j], dp[t][j - price[k]] + like[k]);
                }
                else {
                    dp[t][j] = max(dp[t][j], dp[t^1][GIJUN+(j-price[k])] + like[k]);
                }
            }
            if(j==GIJUN-1) {
                t^=1;
                j=-1;
                //memset(dp[t],0,sizeof(dp[t]));
            }
        }

        if(j-1>=0) printf("%d\n", dp[t][j-1]);
        else printf("%d\n", dp[t^1][GIJUN-1]);

    }
    return 0; 
}

책을 본 이후의 수정 코드#

상태공간을 복잡하게 dp[2][201]로 나타낼 필요 없이, 나머지 연산으로 dp[201] 상태공간만 유지하면 간단하게 해결되는 것을 알게 됨. %연산은 시간이 좀 소요돼서 bit연산으로 수정했고, 상태공간도 201에 가까운 256으로 잡지 않고(%연산을 bit연산으로 수정했기 떄문에 2의 배수로 잡아야 했음.), 1<<16 정도로 대충 크게 잡음.

#include <bits/stdc++.h>
using namespace std;
int price[21], like[21];
int n, m;
const int MASK = (1 << 16) - 1;
int dp[MASK + 1];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> n >> m;
        m /= 100;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) {
            cin >> price[i] >> like[i];
            price[i] /= 100;
        }
        for(int i = 0; i <= m; i++) {
            int& result = dp[i & MASK];
            for(int j = 0; j < n; j++) {
                if(i - price[j] >= 0) {
                    result = max(result, dp[(i - price[j]) & MASK] + like[j]);
                }
            }
        }

        printf("%d\n", dp[m & MASK]);
    }
    return 0;
}