[BOJ 2109, Python 3] 순회강연

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

2109번: 순회강연

 

두 가지 풀이가 존재 합니다.

풀이1 4516ms

풀이2 632ms

 

풀이 1

내림차순으로 정렬하고, 입력값에 나온 가장 큰 일수를 찾아 visit 배열의 크기로 설정해둔다음

내림차순한 배열을 for문으로 돌리면서 1일~x일에 예약을 할 수 있는지 for문으로 확인해봅시다.

예약할 수 있으면 하고, 아니면 넘어갑니다. 이러면 2중for문 코드가 되는데 이게 통과하네요.

 

코드 1

n = int(input())
if n == 0:
    print(0)
    exit()
arr = sorted([[*map(int, input().split())] for _ in range(n)], reverse=True)
max_day = max(arr[i][1] for i in range(n)) + 1
ans = 0
visit = [0] * max_day
for val, day in arr:
    for i in range(day, 0, -1):
        if not visit[i]:
            visit[i] = 1
            ans += val
            break
print(ans)

 

풀이 2

이번엔 날짜를 기준으로 오름차순 정렬을 합니다.

그리고 최소힙을 이용해서 값을 추가하다가 (최소힙에 들어있는 원소의 개수) > (배열에 있는 날짜)일 경우 하나를 빼서 값을 같게 해야하기 때문에 제일 적게 벌 수 있는 강연을 버리게 하면 됩니다.

 

풀이 1은 금액과 날짜를 내림차순하여 가장 큰 금액을 가진 것부터 확인하고, 풀이 2는 최소힙을 이용하여 힙에 값을 저장하다가 가장 작은 금액을 버리게 하는 것으로 과정만 다를 뿐이지 결과는 같습니다.

코드 2

from heapq import *
n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)], key=lambda x:x[1])
ans = []
for pay, day in arr:
    heappush(ans, pay)
    if len(ans) > day: heappop(ans)
print(sum(ans))