-
백준 1202 보석 도둑 (boj/1202.cpp)R&E: research & education/PS 2024. 1. 30. 01:00
그리디, 이진탐색을 엮은 문제입니다.
union-find의 find알고리즘을 조금 차용하여 구현했습니다.
보석이 들어갈 수 있는 가장 작은 가방을 찾은 다음, 그 가방보다 크기가 크거나 같고 && 비어있는 가방을 찾습니다. 이때 비어있다의 조건은 nxt[cur]==cur입니다.
#include <iostream> #include <algorithm> #include <vector> using namespace std; int N, K; vector< pair<int, int> > J; vector< int > nxt; vector< int > B; int find(int cur){ if(cur>=K || nxt[cur]==cur){ return cur; } return nxt[cur]=find(nxt[cur]); } void put(int cur){ if(cur>=K){ return; } if(nxt[cur]==cur){ nxt[cur]=find(cur+1); } else{ put(nxt[cur]); nxt[cur]=find(nxt[cur]); } } int bnsrc_S(int val){ int lft=0, rht=K-1, mid; for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){ if(mid==0){ return val>B[mid]; } if(B[mid-1]<val && val<=B[mid]){ return mid; } else if(val<=B[mid-1]){ rht=mid-1; } else{ lft=mid+1; } } return K; } int main(void){ int M, V, C; int idx; long long sum; ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>N>>K; J.resize(N); B.resize(K); nxt.resize(K); for(int i=0;i<N;i++){ cin>>M>>V; J[i]=make_pair(V, M); } for(int i=0;i<K;i++){ cin>>C; B[i]=C; nxt[i]=i; } sort(J.begin(), J.end()); sort(B.begin(), B.end()); sum=0; for(int i=N-1;i>=0;i--){ V=J[i].first; M=J[i].second; idx=bnsrc_S(M); if(idx>=K || find(idx)>=K){ continue; } sum+=V; put(idx); } cout<<sum; return 0; }
'R&E: research & education > PS' 카테고리의 다른 글
백준 7469번 K번째 수 (boj/7469.c) (1) 2024.01.23 백준 6987번 월드컵 (boj/6987.c) (0) 2024.01.23 백준 1310번 달리기 코스 (boj/1310.cpp) (1) 2024.01.22 백준 13977번 이항 계수와 쿼리 (boj/13977.c) (1) 2024.01.21 백준 1786번 찾기 (boj/1786.c) (0) 2024.01.18