[알고리즘 문제 풀이][탐욕] 백준 2109번 - 순회강연

백준 2109번 순회강연 문제입니다.

(탐욕 알고리즘 or 우선순위 큐)

 

- 문제 설명: https://www.acmicpc.net/problem/2109

- 문제 풀이:

 

본 문제는 탐욕 알고리즘 혹은 우선순위 큐로 풀이 가능합니다. (시간이 2초이고, 입력 크기가 10,000 이므로 N^2 알고리즘 가능)

 

탐욕 알고리즘을 쓰는 경우에는 pay 가 큰 값부터 작은 값으로 정렬해주고 (d일 이내에 와야한다는 조건 때문에 오름차순이 아닌 내림차순으로 풀이하게 됩니다), pay 가 큰 값부터 우선적으로 day 에 지정해줍니다. 그런데, day 값을 그 기간 안에 오기만 하면 되는 것이기 때문에 1일차부터 주어진 day 까지 다 확인하면서 지정해줍니다.

(자세한 설명: https://steady-coding.tistory.com/231)

 

우선순위 큐를 쓰는 경우에는 강연이 가능한 가장 마지막 날부터 강연을 요청한 곳들의 pay 를 우선순위 큐에 넣습니다. 그 중 가장 pay를 크게 주는 값을 pop 합니다. 그리고 그 전 날짜로 가면서 우선순위 큐에 그 전 날짜들의 pay 를 추가합니다. 이들 중에 또 가장 pay 를 크게 주는 값을 pop 합니다. 이런식으로 1 일차까지 정해지도록 하면 됩니다.

(자세한 설명: https://velog.io/@ha-mulan/%EB%B0%B1%EC%A4%80-2109%EB%B2%88-%EC%88%9C%ED%9A%8C%EA%B0%95%EC%97%B0)

 

- 코드: 

탐욕 알고리즘

visited = [0]*10001

N = int(input())
pos = []
for i in range(N):
    pos.append(list(map(int, input().split())))

ans = 0

if len(pos):
    pos.sort(key = lambda x: -x[0])
    for i in range(N):
        for j in range(pos[i][1], 0, -1): # 1 일차까지만
            if visited[j] == 0:
                ans += pos[i][0]
                visited[j] = 1
                break

print(ans)

 

우선순위 큐

(출처: https://www.acmicpc.net/source/18112650)

from heapq import *

n = int(input())
tasks = [[] for i in range(10001)]
for i in range(n):
    p, d = map(int,input().split())
    tasks[d].append(p)
heap = []
ans = 0
for i in range(10000, 0, -1):
    for x in tasks[i]: heappush(heap, -x)
    if heap: ans+= -heappop(heap)
print(ans)

 

 

- 실수 포인트 & 반례:

1. 인덱스 에러

코드에서 10000 일이 들어올 수 있는 것을 고려해서 배열 크기를 10001로 잡지 않고, 10000 까지만 잡는 경우 발생할 수 있습니다.

 

2. 또 다른 인덱스 에러

입력으로 0이 들어온 경우, 0을 출력해야하는데, 코드에서 이 부분을 처리하지 않으면 python 코드로 로직을 짰을 때 인덱스 에러가 발생할 수 있습니다.

 

3. d 일 안에 오기만 하면 된다는 조건을 d 일째에 가야하는 것으로 착각한 경우 발생할 수 있는 반례가 있습니다.

입력
3
1 1
10 2
10 2
정답 20

입력
3
70 3
60 3
50 3
정답 180

입력
4
70 3
60 3
50 3
40 3
정답 180

입력
4
20 2
30 2
40 3
40 3
정답 110