[백준] 9569 - No Change (c++)

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

 

문제 요약

사야 하는 물건 N개와 들고 있는 동전 K개의 가치가 주어진다. 꼭 순서대로 사야하며 여러개를 한 번에 살 수 있다. 또한 거스름돈을 받을 수 없다. 이 때 남기는 돈의 최대값을 구해라.

 

풀이 (2^KlogN)

• 비트dp
• 누적합
• 이분탐색

dp[k];  dp[i]=동전 비트마스크가 i일 때 살 수 있는 물건의 최대 개수로 정의 해준다. 물건 가격의 누적합 배열을 만들어 두면 이분탐색으로 logN에 업데이트를 해줄 수 있다. upper_bound(all(psum),psum[이미 먹은 개수]+쓸 동전 가치) 이렇게

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int k,n;cin>>k>>n;
    int c[k],p[n],ps[n+1]{},sum=0;
    for(int& x:c) cin >>x,sum+=x;
    int i=1;
    for(int& x:p) cin>> x,ps[i++]=ps[i-1]+x;

    array<int,2> dp[1<<k]{};
    int ans =-1;
    for(int i=1;i<1<<k;i++) {
        for(int j=0;j<k;j++) if(i&1<<j){
            auto pre=dp[i^1<<j];
            dp[i][0]=max(dp[i][0],int(upper_bound(ps+1,ps+n+1,ps[pre[0]]+c[j])-ps)-1);
            dp[i][1]=pre[1]+c[j];
            if(dp[i][0]==n) ans=max(ans,sum-dp[i][1]);
        }
    }   
    cout<<ans;
}