[그리디] 13904 과제 (파이썬)

🥕 [ 백준 13904 ] 과제

문제 링크

url : https://www.acmicpc.net/status?user_id=beagentleman7&problem_id=13904&from_mine=1 

채점 현황

 

🍒 문제 분석

기간과 점수가 정해진 문제를 풀 때 어떤 것을 우선순위로 해서 풀어야할까?

전형적인 그리디 문제이다.

 

🥑 코드

N = int(input())
homeworks=[]
for _ in range(N):
    d, w = map(int,input().split())
    homeworks.append((d,w))

homeworks.sort(reverse=True, key=lambda x : x[1])

score=0
days=[0]*1001

for homework in homeworks:
    for d in range(homework[0], 0, -1):
        if days[d] == 0 :
            days[d] = 1
            score += homework[1]
            break
print(score)

 

🍓 내 해결 과정

첫 번째 우선 순위

먼저 점수를 우선순위로 정렬했습니다.

[(4, 60), (2, 50), (4, 40), (3, 30), (1, 20), (4, 10), (6, 5)]

 

그 후 FOR 문을 돌려 각 과제에 대해 어느날 할지를 결정합니다.

 

두 번째 우선순위

마감 기한이 그 다음 결정 기준이 됩니다.

가령 (4, 60)의 경우 4일차에 하는게 바람직합니다.

 

왜냐고요? ( 4, 60 ) 의 경우 스코어가 높으므로 반드시 해야하는 과제인데, 마감 기한인 4일차에 함으로써 1일, 2일, 3일 차에는 다른 과제를 할 수 있게 되기 때문입니다.

 

이후 (2,50) 은 2일차에, (4,40) 은 4일차 스케쥴이 이미 있으니 3일차에 하게 되는 것입니다.

 

그리고 (3,30)의 경우 2, 3, 4 일차 스케쥴이 채워져있으므로 1일차에 하면 됩니다.

 

아이디어를 떠올리면 단순해지는 그리디 문제 였습니다.