뚝딱뚝딱

소프티어 lv2 "금고 털이" 문제 풀이 중 pair vector와 sort사용이 익숙치 않아 정리하는 글이다.

pair vector

vector<pair<int, int>> v;

vector에서는 한 요소에 두가지 값을 함께 넣으려면, 위와 같이 pair로 묶어서 정의해 주어야 한다.

"금고 털이" 문제에서 첫번째 int 요소에는 금속의 무게를 , 두번째 int 요소에는 금속의 가치를 저장해주었다.

각각의 값에 접근하려면, v.first, v.second로 접근할 수 있다.

sort

algorithm에서 정의한 정렬 함수 sort이다.

기본적으로 오름차순 정렬이고, pair vector의 경우 첫번째 값을 기준으로 오름차순 한다.

sort(v.begin(), v.end());

이렇게 하면 vector v를 첫번째 값인 금속 무게에 대해서 오름차순 정렬해준다.

그런데 나는 금속의 가치인 두번째 값에 대해서 내림차순 정렬하고 싶었다.

그래서 sort함수에, 따로 정의한 비교함수를 인자로 넣어, 이 기준으로 정렬해 주세요~라고 요청했다.

bool compare(const pair<int, int> &a, const pair<int, int> &b){
	return a.second>b.second;
}

 위와 같은 compare 함수를 정의해 주었다.

내가 헷갈렸던 점은, 부등호의 방향이다. 

처음에는 b쪽에 크다고 했는데, 이유는 정렬할 때 뒤에 있던게 컸었다..라고 생각한 것이다. 아무튼 나의 착각이고..

내림차순이 앞이 큰거니까, 먼저 위치한 a가 클 때 true로 정의해 주는 것이다.

반대로 오름차순이면? b쪽으로 부등호가 향해야 할 것이다.

이렇게 해서 기본 of 기본인 pair vector와 sort함수에 대해 정리해보았다.

다음에는 버벅거리지 않고 바로 구현하길~

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 벡터 정렬만 할 줄 알면 되므로, 아주 쉽다.