백준 2109 c++ "순회강연" -PlusUltraCode-

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

 

 

[필자 사고]

money 와 day가 주어졌다.

이 문제를 보고 예전에 풀어본 비슷한 문제가 떠올랐다.

가자 비싼 값어치를 우선 정렬뒤 같은 값일 경우 day가 큰걸로 정렬했다.

그후 첫번째 idx를 꺼내 nowDay 부터 day ==1 까지 비어있는 것중 가장 큰 day 에다가 값을 넣었다.

 

처음 보면 한번에 풀기는 쉽지 않은 알고리즘이지만 한번만 제대로 이해한다면 수월하게 문제를 풀 수 있다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 강연 정보를 입력받고, 문제 해결을 위한 준비 작업을 수행하는 함수이다.
먼저 사용자로부터 강연 요청의 개수 N을 입력받는다. 이후 N개의 줄에 걸쳐 각 강연에 대한 정보, 즉 강연료(num)와 가능한 마지막 날짜(day)를 입력받는다. 이 두 값은 pair<int, int> 형태로 arr 벡터에 저장된다.

모든 입력이 끝나면 visited 벡터를 false로 초기화하며, 이는 날짜별로 해당 날짜에 강연이 배정되었는지를 추적하기 위해 사용된다. 배열 크기는 문제 조건상 최대 날짜가 10,000일 수 있으므로 10,001로 설정된다.

마지막으로 arr 벡터는 사용자 정의 비교 함수 cmp에 따라 정렬된다. 이 비교 함수는 강연료가 큰 순서대로, 강연료가 같다면 가능한 날짜가 늦은 순서대로 정렬되도록 구성되어 있다. 이를 통해 가장 이득이 큰 강연을 먼저 고려할 수 있도록 우선순위가 정해진다.

---

2. 강연 일정 배정 및 최대 수익 계산 (Game_Start 함수)

Game_Start() 함수는 정렬된 강연 리스트를 기반으로 가장 많은 강연료를 얻을 수 있도록 일정을 배정하는 역할을 수행한다.
이 함수는 resultMoney라는 변수를 통해 누적 강연료를 계산한다.

각 강연에 대해 가능한 날짜 (nowDay)에서 시작하여 거꾸로 1일까지 순회하며 아직 비어 있는 날(visited[day] == false)을 찾는다. 해당 날짜가 비어 있다면 그 날짜에 강연을 배정하고 visited[day]를 true로 설정한다. 이후 해당 강연료를 resultMoney에 더한 후, 더 이상 이 강연에 대해 탐색하지 않고 다음 강연으로 넘어간다.

이러한 방식은 그리디 알고리즘의 전형적인 형태로, 가장 값비싼 강연을 가능한 가장 늦은 날짜에 배치함으로써 이후에 더 이득이 적은 강연들을 앞쪽 날짜에 배치할 수 있도록 여유를 남겨 둔다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
typedef pair<int, int> Node;
vector<Node> arr;
vector<bool> visited;

bool cmp(Node a, Node b) {
	if (a.first == b.first) {
		return a.second > b.second;
	}
	return a.first > b.first;

}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++ ) {
		int num, day;
		cin >> num >> day;
		arr.push_back({ num,day });
	}

	visited.resize(10001, false);
	sort(arr.begin(), arr.end(), cmp);
}

void Game_Start() {
	long resultMoney = 0;
	for (int i = 0; i < arr.size(); i++) {
		int nowDay = arr[i].second;
		int nowMoney = arr[i].first;
			
		for (int day = nowDay; day >= 1; day--) {
			if (visited[day] == false) {
				visited[day] = true;
				resultMoney += nowMoney;
				break;
			}
		}
	}

	cout << resultMoney;
}

int main(void) {
	Input();
	Game_Start();
}