[BOJ] 백준 2109번 : 순회강연 (JAVA)

문제

한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다.

 

각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다.

 

이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

 

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

 

 

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

 

 

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

 

 

풀이

그리디 알고리즘으로 풀 수 있는 문제였습니다.

 

 

먼저, 우리는 직관적으로 비용이 큰 순서대로 내림차순 정렬을 하면 좋겠다는 생각을 할 수 있습니다.

 

하지만, d일 안에 강연을 선택하는 것이지, 꼭 d일째에만 강연을 선택하는 것이 아니기 때문에 비용이 큰 순서대로 내림차순 정렬을 하고 추가적인 탐색이 필요합니다.

 

문제의 조건을 보면, n이 10,000으로 충분히 작고 시간 제한이 2초이므로 O(N²)으로도 문제를 해결할 수 있어 보입니다.

 

따라서, 비용이 큰 순서로 정렬하되, 그 비용에 해당하는 날짜를 역순으로 1일까지 탐색하면서 들어갈 자리가 있는지 확인하면 됩니다.

 

이 부분은 문제의 예시를 통해 이해해 봅시다.

 

문제의 예시를 비용이 큰 순서로 정렬하면 아래와 같습니다.

 

 

100 2
50 10
20 1
10 3
8 2
5 20
2 1

 

 

처음에 아무 스케줄도 없기 때문에 2번째 날에 비용 100짜리 강연 스케줄을 잡습니다.

 

비용 50은 10번째 날에 해당하는데 10번째 날에 스케줄이 없으므로 스케줄을 잡습니다.

 

비용 20은 1번째 날에 해당하는데 1번째 날에 스케줄이 없으므로 스케줄을 잡습니다.

 

비용 10은 3번째 날에 해당하는데 3번째 날에 스케줄이 없으므로 스케줄을 잡습니다.

 

비용 8은 2번째 날에 해당하는데 이미 1, 2번째 날에 스케줄을 잡았으므로 이 강연은 패스합니다.

 

비용 5는 20번째 날에 해당하는데 20번째 날에 스케줄이 없으므로 스케줄을 잡습니다.

 

비용 2는 1번째 날에 해당하는데 1번째 날에 스케줄을 잡았으므로 이 강연은 패스합니다.

 

따라서, 100 + 50 + 20 + 10 + 5 = 185 가 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.