[Greedy] 백준 - 과제 13904번

😒 문제 요약

하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

😂 key point

대표적인 그리디 문제이다. 그리디의 많은 문제들이 정렬을 이용하여 풀면 편하게 풀 수 있으므로 마감일을 기준으로 오름차순으로 정렬하여 과제를 할 수 있는지 여부를 판단하여 풀었다. 자세한 것은 코드 주석에서 설명하겠다.

🎂 코드

n = int(input())

lst = []

for _ in range(n):
    lst.append(list(map(int, input().split())))

lst.sort()

# 과제를 선택해서 높은 배점에 문제만 골라야 할 때 0
flag = 0

result = []

for i in lst:
    flag = i[0] - len(result)
    
    if flag != 0:
        result.append(i[1]) 
        
    #과제를 선택해 높은 배점에 문제만 골라야 할 때
    else:
        # 만약 높은 배점에 문제라면 제일 작은 배점 문제 제외시킨다. 
        result.sort(reverse=True)
        
        if result[-1] < i[1]:
            result.pop()
            result.append(i[1])

print(sum(result))