백준 2073 수도배관공사 C++

 

간단한 해설

 

간단하게 문제를 보면 단순히 배낭문제라 생각할 수 있고, 풀이는 다음과 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int d,p;

    cin>>d>>p;

    vector<pair<ll,ll>> v(p);

    for(int i=0;i<p;++i){
        cin>>v[i].first>>v[i].second; // length, capacity
    }

    vector<vector<ll>> dp(p+1,vector<ll>(d+1,0)); // gae, length

    for(int i=1;i<=p;++i){
        for(int j=0;j<v[i-1].first;++j){
            dp[i][j]=dp[i-1][j];
        }

        dp[i][v[i-1].first]=dp[i-1][v[i-1].first]==0?v[i-1].second:max(dp[i-1][v[i-1].first],v[i-1].second);
        for(int j=v[i-1].first+1;j<=d;++j){
            dp[i][j]=max(dp[i-1][j],min(dp[i-1][j-v[i-1].first],v[i-1].second));
        }
    }

    ll ans=0;
    for(int i=1;i<=p;++i){
        ans=max(ans,dp[i][d]);
    }
    cout<<ans;

}

 

그러나 문제에서 주어진 메모리는 128MB이므로,

이 문제를 2차원 dp로 풀고자 하면, 350*10만 하면 3500만이고 int로 하면 약 140mb, long long으로 하면 그 두배인 280mb정도의 메모리를 사용하게 되어서 메모리 초과가 발생한다.

 

그럼 이를 어떻게 해결할까??

 

단순히 슬라이딩 윈도우 기법을 사용하면 된다.

 

아까 작성한 2차원 dp 코드에서 사실 계산에서 사용하는 배열은 이전 배열과 현재 배열(dp[i-1]과 dp[i])밖에 없다.

 

그러므로 두 가지만 따로 변형해서 계산해나가면 된다.

 

 답

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int d,p;

    cin>>d>>p;

    vector<pair<ll,ll>> v(p);

    for(int i=0;i<p;++i){
        cin>>v[i].first>>v[i].second; // length, capacity
    }
    
    vector<ll> beforeDP(d+1,0);
    vector<ll> afterDp(d+1,0);

    for(int i=1;i<=p;++i){
        for(int j=0;j<=d;++j){
            afterDp[j]=0;
        }

        for(int j=0;j<v[i-1].first;++j){
            afterDp[j]=beforeDP[j];
        }

        afterDp[v[i-1].first]=beforeDP[v[i-1].first]==0?v[i-1].second:max(beforeDP[v[i-1].first],v[i-1].second);

        for(int j=v[i-1].first+1;j<=d;++j){
            afterDp[j]=max(beforeDP[j],min(beforeDP[j-v[i-1].first],v[i-1].second));
        }

        for(int j=0;j<=d;++j) beforeDP[j]=afterDp[j];
    }

    cout<<afterDp[d];

}