[백준] 2109번 순회 강연 (C++)

 

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

 

문제 설명

대학에서 p만큼의 강연료를 지불할테니 d일 이내에 와서 강연을 해달라는 조건이다.
최대한 많은 돈을 벌 수 있게끔 구하는 문제이다. 

 

주요 로직

1. 강연료를 기준으로 방문할 대학을 고른다.
-> sort() 함수를 이용해 강연료를 내림차순으로 정렬한다. 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,d,p,ret;
bool arr[10004];
vector<pair<int,int>> v;

bool cmp(pair<int,int> a, pair<int,int> b){
	return a.first > b.first;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> p >> d;
		v.push_back({p,d}); // d일, p값 
	}
	
	sort(v.begin(), v.end(), cmp);

	for(int i=0; i<n; i++){
		if(arr[v[i].second] == false){
			arr[v[i].second] = true;
			ret += v[i].first;
		}
		else{
			for(int j=v[i].second-1; j>0; j--){
				if(arr[j] == false){
					arr[j] = true;
					ret += v[i].first;
					break;
				}
			}
		}
		
	}
	
	cout << ret << "\n";

}