[백준 13904] 과제 - 골드1(그리디, 정렬)

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

13904번: 과제

 

• 사용한 자료구조: 리스트
• 사용한 알고리즘: 정렬, 그리디

 

문제를 풀다가 이번 코드는 이제껏 한 번도 사용해본 적 없는 방법으로 푼 문제라 기록해두고 싶어서 오랜만에 알고리즘 포스팅을 한다.

 

원래 이 문제는 우선순위 큐를 사용해서 푸는 문제지만, 나는 리스트의 정렬만으로 문제를 풀이했다.

먼저, 이 문제에서의 데이터의 우선순위는 (1) 과제의 점수가 높을 수록, (2) 마감 기한이 짧을수록 높기 때문에 입력을 받으며 lambda 식으로 정렬해 주었다.

 

문제는 아래 예제에서 다음과 같이 드러난다.

빨간색으로 표시된 부분들은 과제 점수를 최대로 받기 위해 수행해야 하는 과제들인데, 데이터를 정렬한 상태에서 순차적으로 과제를 수행한다면 1일 차에 [4, 60]을, 2일 차에 [2, 50]을, 3일 차에 [4, 40]을 수행하게 되어 [3,30]의 과제는 4일 차이기 때문에 마감 기한이 지나서 수행할 수 없다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

정렬: [[4, 60], [2, 50], [4, 40], [3, 30], [1, 20], [4, 10], [6, 5]]
정답: [[4, 60], [2, 50], [4, 40], [3, 30], [1, 20], [4, 10], [6, 5]] = 185점
오답: [[4, 60], [2, 50], [4, 40], [3, 30], [1, 20], [4, 10], [6, 5]] = 155점

 

따라서, 과제를 순차적으로 수행하여서는 안 되겠다는 결론이 나온다.

이 문제를 해결하기 위해 사용한 방법은 과제 수행을 최대한 마감일에 가깝게 해야 이후의 과제들을 수행할 수 있는 가능성이 높아진다는 점을 이용하여 1000일 동안의 과제 수행 점수를 기록해 두는 리스트를 만드는 것이다. (문제 조건에서 1≤d≤1000)

 

>> 풀이 과정

1. 정렬된 과제들을 순차적으로 탐색한다.
2. 해당 과제 마감일에 아직까지 수행한 과제가 없다면 과제를 수행한다.
3. 해당 과제 마감일에 이전에 수행한 과제가 있다면 1~(과제 마감일)까지 과제를 수행할 수 있는 최대 날짜를 찾고, 그날에 과제를 수행한다.
4. 모든 탐색이 끝나면 수행했던 과제들의 점수를 모두 합한다.

 

>> 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
tasks = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (-x[1], x[0]))

scores = [0 for _ in range(1001)]
for d, w in tasks:
    if scores[d] == 0:
        scores[d] = w
    else:
        for i in range(d, 0, -1):
            if scores[i] == 0:
                scores[i] = w
                break

print(sum(scores))

 

 

이 문제를 풀기 위한 아이디어를 찾다가 발견한 알아두면 좋은 팁이 인상 깊어서 메모하고 싶다.

문제를 풀기 전에, 다이나믹 프로그래밍으로 풀 건지, 그리디로 풀 건지 먼저 판단해야 된다. 전에 공부했을 때 이 두 알고리즘을 구분하는 기준은, 데이터를 가지고 순서대로 판단을 해볼 때 지금 이 데이터를 포기함으로써 나중에 이득을 보게 될 수 있는가 라고 정리했었다. 이 문제의 경우에는 일단은 무조건 좋은 점수를 먹는 게 중요하기 때문에 다이나믹 프로그래밍보다는 그리디가 어울린다.

출처) https://velog.io/@heyksw/Python-백준-gold-13904-과제