[python 백준 13904] 과제

📜 접근 방법

1. 날짜순으로 오름차순 정렬
2. 제일 긴 마감일 찾기
3. 그 날로부터 가능한 과제 중 제일 높은 점수 고르기

모든 과제 : [1, 20], [2, 50], [3, 30], [4, 60], [4, 40], [4, 10], [6, 5]

6일째에 수행 가능한 과제 : [6, 5]

5일째에 수행 가능한 과제 : X

4일째에 수행 가능한 과제 : [4, 60], [4, 40], [4, 10]

3일째에 수행 가능한 과제 : [3, 30], [4, 40], [4, 10]

2일째에 수행 가능한 과제 : [2, 50], [3, 30], [4, 10]

1일째에 수행 가능한 과제 : [1, 20], [3, 30], [4, 10]

최대 총 점수 : 185

 

❌1일차 부터 하면 안되는 이유!

모든 과제 : [1, 20], [2, 50], [3, 30], [4, 60], [4, 40], [4, 10], [6, 5]

1일째에 수행 가능한 과제 : [1, 20], [2, 50], [3, 30], [4, 60], [4, 40], [4, 10], [6, 5]

2일째에 수행 가능한 과제 : [2, 50], [3, 30], [4, 40], [4, 10], [6, 5]

3일째에 수행 가능한 과제 : [3, 30], [4, 40], [4, 10], [6, 5]

4일째에 수행 가능한 과제 : [4, 10], [6, 5]

5일째에 수행 가능한 과제 : [6, 5]

6일째에 수행 가능한 과제 : X

최대 총 점수 : 165

 

✅ 정답 코드

import sys

n = int(sys.stdin.readline())

subject = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

subject.sort(key= lambda x : x[0])

deadline = subject[n - 1][0]
total = 0

while deadline > 0:
    check = -1
    max_score = 0
    for i in range(len(subject)):
        if subject[i][0] >= deadline:
            if max_score <= subject[i][1]:
                max_score = subject[i][1]
                check = i
    if check != -1:
        total += max_score
        subject.remove(subject[check])
    deadline -= 1
print(total)

 

 

💡알게 된점

기본적으로 정렬을 하면 어느정도 갈피가 잡히는거 같다.
그리디 알고리즘을 사용해야하는 것을 알았다.
접근 방법을 어떻게 해야하나 고민하다가 찾아봤는데 내가 생각했던 방법과 비슷해서 좀 아쉬웠다. 좀 더 생각해볼걸,,,