백준[13904] 과제 (Python3)

큐 + 정렬로 풀었는데 태그 까보니 우선순위 큐로도 풀 수 있었던 문제
N의 범위가 작기 때문에 완전 탐색으로 풀 수 있다.

지문 분석

최대한 점수를 많이 주는 과제를 해결해야 한다.
단, 기한이 충분하다면 기간이 얼마 안 남은 다른 과제를 푸는 게 더 유리한지 확인한다.

완전 탐색

날짜를 기준으로 오름차순 정렬한다.
N 개의 -1 원소를 갖는 일차원 배열을 선언한다. 각 인덱스는 1일, 2일 ... N일이다.
만약 그날 얻을 수 있는 점수가 -1이고, 제출 기한 내라면, 현재 과제 점수를 넣는다.
그게 아니라면, 1일부터, 그 이전까지 얻은 과제 중 최솟값을 찾아 교체한다.
이를 반복하면 O(N ^ 2)로 해결 가능하다.

 

def main():
    N = int(input())
    works = []
    for _ in range(N):
        d, w = map(int, input().split())
        works.append((d, w))
    works = sorted(works, key=lambda x: x[0])
    schedules = [-1] * N
    for i in range(N):
        work_index, work_score = works[i]
        if schedules[i] == -1 and i + 1 <= work_index:
            schedules[i] = work_score
        else:
            minScore, minIndex = float("inf"), -1
            for j in range(work_index):
                if schedules[j] < work_score and schedules[j] < minScore:
                    minScore, minIndex = schedules[j], j
            if minIndex != -1:
                schedules[minIndex] = work_score
    ans = 0
    for schedule in schedules:
        if schedule != -1:
            ans += schedule
    print(ans)



if __name__ == "__main__":
    main()