[알고리즘] BOJ 13904 과제

[BOJ] 13904 과제 문제 바로가기

📍 문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

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

📍 입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

📍 출력

얻을 수 있는 점수의 최댓값을 출력한다.

---

📍 풀이

• 입력받은 마감일과 과제 점수를 배열에 입력한 뒤 sort(key = lambda x : x[1])를 이용하여 과제 점수 기준으로 정렬합니다.
• 입력받은 마감일 중 가장 큰 값을 기준으로 일정을 다룰 배열을 생성합니다.
• 과제 점수가 가장 큰 과제부터 차례로 일정 배열에서 현재 마감일 기준으로 이전의 날짜가 비어있다면 일정 배열에 추가합니다.
• 모든 과정이 끝난 후 일정 배열에 존재하는 원소들의 값을 더합니다.

✍ 코드

from sys import stdin

N = int(stdin.readline())
A = [] # 마감일과 과제점수 값을 받을 []
M = 0 # 입력받은 마감일 중 가장 큰 값을 저장할 변수

for _ in range(N):
  d, w = map(int, stdin.readline().split())
  if d > M: # 가장 큰 마감일을 찾는 if
    M = d
  A.append([d,w])
result = [False for _ in range(M+1)] # 결과값을 저장할 []

A.sort(key = lambda x : x[1]) # 과제 점수 순으로 정렬

for i in range(N-1,-1,-1):
  for j in range(A[i][0],0,-1): 
    if result[j] == False: # 마감일 이전의 일정에 빈 곳이 있다면
      result[j] = A[i][1] # 과제 점수 입력
      break
print(sum(result)) # 일정표에 작성된 과제 점수 합