[백준] 2109번 - 순회강연 (파이썬)

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

 

# 순회강연
import sys
input = sys.stdin.readline

N = int(input())
info = []

max_day = 0
for _ in range(N):
    pay, day = map(int, input().split())
    max_day = max(max_day, day)
    info.append((day, pay))
info.sort(key=lambda i: (i[1], i[0]))

possible = [True for i in range(max_day+1)]
result = 0
for _ in range(N):
    day, pay = info.pop()
    for d in range(day, 0, -1):
        if possible[d]:
            possible[d] = False
            result += pay
            break

print(result)

 

그리디, 정렬
1. 정보를 info에 입력받고 day의 최댓값을 max_day에 저장
2. day를 기준으로 오름 차순 정렬, day가 같다면 pay를 기준으로 오름차순 정렬 (pop을 이용하기에 오름차순)
3. possible : 해당 날짱에 방문 가능 한지의 여부
4. N만큼 for문
    - info를 하나씩 pop
    - 1일부터 ~ 해당 날짜까지 방문 가능한 가장 마지막 날짜를 탐색
        - 해당 날짜의 possible을 False로 설정
        - result += pay
        - break
5. result 출력

 

문제를 읽자마자 떠오르는 아이디어의 흐름대로 풀이를 했다.

우선순위 큐를 사용할까 하다가 그냥 람다 함수를 통한 정렬을 이용해서 그리디로 접근을 했다.

방문 가능한 가장 마지막 날짜를 탐색할 때, 최악의 경우에도 시간 복잡도를 만족한다.

(N = 10000, max_day = 10000)

 

정렬의 키 속성에 람다 함수를 이용해서 내부에 리스트나 튜플을 이용해서 우선순위를 설정할 수 있다.

가장 값의 속성을 이용해 정렬을 하고 그 값이 같은 정보들 중 두 번째 속성을 이용해서 정렬을 하고...