[백준] 3362 - 수수께끼 (c++)

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

 

문제 요약

N과 K, N개의 동전 가치가 주어진다. 동전을 처음부터 연속으로 사용해서 최소 몇번 동전까지 쓰면 1~K까지 모든 가치를 만들 수 있는지 구해라.

 

풀이 (NlogK)

• 매개 변수 탐색
• 그리디

동전을 정렬하고 나면 가치를 몇까지 만들 수 있는지 알 수 있다. 현재 가치를 x까지 만들수 있고 다음에 가치가 y인 동전이 오면 x+y까지 만들 수 있다. 하지만 만약 x+1<y면 중간에 못 만드는 가치가 생기게 되는데, 그 인덱스가 y이하가 되기 때문에 정렬한 상태론 못 만들게 된 가치는 뒤에서도 만들 수가 없게 된다. 이런 방식으로 인덱스가 i이하인 동전만 써서 K를 만들 수 있냐?로 파라메트릭을 돌리면 된다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    while(t--) {
        int n,k;cin>>n>>k;
        array<int,2> a[n];
        int i=1;
        for(auto& [x,y]:a)cin>>x,y=i++;
        
        sort(a,a+n);
        int l=0,r=1e6;
        while(l<=r) {
            int mid =l+r>>1;
            bool can=1;
            int sum=0;
            for(auto& [x,y]:a) {
                if(y>mid)continue;
                if(x<=sum+1)sum+=x;
                else{can=0;break;}
                if(sum>=k)
                    break;
            }
            if(can&&sum>=k)
                r=mid-1;
            else    
                l=mid+1;
        }
        cout<<(l==1e6+1?-1:l)<<'\n';
    }
}