반응형
https://softeer.ai/practice/6288
💡 금고 털이
- 무게가 W인 배낭, N개의 금속 종류가 있다.
- 최대의 가치를 갖도록 금속을 담는데, 무게 W를 넘지 않아야 한다.
- 금속은 1g당 가치를 갖는다.
- 따라서 높은 가치를 갖는 순서대로 배낭에 담아야 한다.
- 금속의 무게와 가치를 갖는 pair 벡터를 이용하였다.
- pair 벡터에서 두번째 요소인 가치에 따라 내림차순 정렬 하기 위해, 비교함수인 compare를 정의해주었다.
- 내림차순 정렬 후, 각 금속에 대해서, 무게가 현재의 W를 넘지 않으면, 그 무게만큼 넣고, 그렇지 않으면 W만큼 떼어다 넣기로 한다. 넣은 무게만큼 W에서 차감하는 방식이다.
전체 코드는 아래와 같다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(const pair<int, int> &a, const pair<int, int> &b){
return a.second>b.second;
}//두번째 요소를 기준으로 내림차순 하도록..
int main(int argc, char** argv)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int W,N;
cin>>W>>N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++){
cin>>v[i].first>>v[i].second;
}
sort(v.begin(), v.end(), compare);//두번째 요소를 통해 compare 하도록 비교함수 정의
int value=0;
for(int i=0; i<N; i++){
if(W==0) break;
int used=(v[i].first<=W)?v[i].first:W;
value+=used*v[i].second;
W-=used;
}
cout<<value;
return 0;
}
pair 벡터 정렬만 할 줄 알면 되므로, 아주 쉽다.
반응형
'CO-TE > 소프티어' 카테고리의 다른 글
[구름 플랫폼] 2023 현대자동차 부트캠프 3기 코딩테스트 예제 풀이 (0) | 2023.11.18 |
---|---|
[소프티어] JAVA LV3 "슈퍼바이러스" 풀이법 / 분할과 정복 (0) | 2023.11.07 |
[소프티어] JAVA LV2 "바이러스" 풀이법 (0) | 2023.11.06 |
[소프티어] c++ LV3 "징검다리" 계수정렬 이용 풀이법 (0) | 2023.11.02 |
[소프티어] c++ LV3 "성적 평균" 풀이법 (제출 오류..?) (0) | 2023.11.01 |