문제 링크 : https://www.acmicpc.net/problem/13904
오랜만에 복습해본 그리디 문제. 그리디만 1주일동안 풀었던 적이 있는데, 그 때 연습한게 도움이 된것 같다. 그때 느꼈던 건, 그리디 문제를 풀 때는 여러가지 방법으로 데이터를 정렬해보고 생각하면 좋다는거다.
문제를 풀기전에, 다이나믹 프로그래밍으로 풀 건지, 그리디로 풀 건지 먼저 판단해야된다. 전에 공부했을 때 이 두 알고리즘을 구분하는 기준은, 데이터를 가지고 순서대로 판단을 해볼 때 지금 이 데이터를 포기함으로써 나중에 이득을 보게 될 수 있는가 라고 정리했었다. 이 문제의 경우에는 일단은 무조건 좋은 점수를 먹는게 중요하기 때문에 다이나믹 프로그래밍보다는 그리디가 어울린다.
그리디라고 방향을 잡았기 때문에, 날짜를 기준으로도 정렬해보고 점수로도 정렬을 해봤다. 잘 생각해보면, 점수로 정렬하는게 맞다.
점수로 내림차순 정렬을 하되, 그 과제를 먹으려면 최대한 나중에 수행하는 쪽으로 구현한다. 예를 들어, (1, 20), (2, 30), (2, 10), (3, 40), (3, 35) 의 과제 데이터가 있을 때, 일단은 제일 점수 높은 (3, 40)을 먹을 생각을 한다. 단, 이 과제를 day = 3 일차에 수행한다고 생각하면서 먹는다. 그래야 day = 1, 2 일차에 먹을 수 있는 과제의 수가 많아지기 때문이다. 만약에 그 과제를 day = 1 일차에 수행한다 치면 day = 1인 과제는 더 이상 먹을 수 없게 되기 때문이다. 그리고 나서는 2번째로 점수가 높은 (3, 35) 를 선택한다. 하지만 이미 day = 3 일차에는 수행할 과제를 확보해놨기 때문에 그 전인 day = 2 일차에 이 과제를 수행하기로 한다.
이런 흐름으로 문제를 풀었더니 정답 처리를 받을 수 있었다. 아래 코드에서 (visit[x] = True) 는 x 일에 과제하기로 처리가 완료 되었다는 뜻이다.
파이썬 코드
import sys N = int(sys.stdin.readline()) homeworks = [] visit = [False] * 1001 for _ in range(N): d, w = map(int, sys.stdin.readline().split()) homeworks.append((d, w)) homeworks.sort(key=lambda x: x[1], reverse=True) answer = 0 for day, worth in homeworks: i = day # 과제를 할 날짜 탐색 while i > 0 and visit[i]: i -= 1 # 과제를 할 날짜가 없으면 패스 if i == 0: continue else: visit[i] = True answer += worth print(answer)
