[백준 BOJ] 13904 : 과제 - python

SUN·2022년 11월 16일

algorithm

목록 보기

27/30

이번에 풀 문제는 과제이다.
이번주 알고리즘 스터디 진행하면서 푼 문젠데, 막혔었는데 풀어내서 뿌듯하다.
예전에는 이런 거 생각도 못했는데 한 3개월 정도 알고리즘 문제를 조금씩이라도 풀다보니
이제 어느정도 문제를 보는 눈이 생긴 것 같다. 풀이 시간은 45분 정도 걸렸다.

문제

풀이과정

일단 점수 순으로 정렬해서 높은 거 부터 넣는 게 기본이 될 거라고 생각했다.
근데 이제 문제는 날짜인데... 이걸 어떻게 해야하지? 하고 한 30분은 고민했다.

머릿속으로는 못떠올리겠어서 노트에다가 그려서 시뮬레이션을 해봤다.
빠른 날짜 순으로 따져보는 것도 안되고.. 무조건 높은 거 부터 넣는 것도 안되고..
마감일이 겹치는 게 있을 수도 있으니 점수가 높은 순으로 보면서 마감일에 처리하는 것도 안됐다.

그러다가 어 그러면 점수가 높은 순으로 보면서 그 과제의 마감일에 처리하려고 하는데,
그 날짜에 이미 다른 작업이 배정돼있으면 바로 전 날에 배정하고 그날도 안되면 또 그 전날에 배정하고... 하면 되지않나?!

하는 생각이 들었고 시뮬레이션 해보니까 딱 됐다.
옛날에 비하면 장족의 발전이다. 뿌듯

알고리즘은

점수가 높은 순으로 max 힙을 구성한다.
힙이 빌 때 까지 반복한다.
1. 힙에서 현재 점수가 가장 높은 과제를 가져온다.
2. 과제 마감일부터 1일 까지 내려가면서 비어 있는 날을 찾는다.
3. 비어있는 날을 찾으면 그 날에 과제를 배정하고 배정했다는 표시를 해준다.

최종 코드

import heapq

n = int(input())

hq = []
max_day = 0
for i in range(n):
    d, w = map(int, input().split())
    heapq.heappush(hq, (-w, d))
    if max_day < d:
        max_day = d

assigned = [False] * (max_day + 1)

score = 0
while hq:
    # 가장 스코어 높은 순으로 가져와서
    w, d = heapq.heappop(hq)
    w = -w

    # d일부터 1일 까지 거꾸로 돌면서 비어있는 날 중에 최대한 늦게 배정
    for i in range(d, 0, -1):
        if assigned[i]:
            continue

        assigned[i] = True
        score += w
        break

print(score)

동작방식을 간단히 설명하자면..

문제의 예시를 점수가 높은 순으로 정렬하면 아래처럼 된다.
(60,4), (50,2), (40,4), (30,3), (20, 1) (10,4), (5,6)

그러니까 처음에는 힙에서 가장 점수가 높은 (60,4)를 가져온다.
이 과제를 최대한 늦게 처리 하려면 4일에 처리해야되고, 4일에 배정된 과제는 없으니 배정한다.

그 다음에 힙에서 (50,2)를 가져온다.
이 과제는 2일에 처리하는 게 제일 늦게 처리하는 거니까 2일에 배정해준다.

다음으로는 (40,4)를 가져온다.
이 과제는 가장 늦게 처리하려면 4일에 처리해야되는데, 4일은 이미 (60,4)과제를 처리하는데 썼다.
그러니까 그 전날인 3일을 본다. 3일에는 아무 과제도 배정이 안됐으니 3일에 배정한다.

그 다음 (30,3)을 가져온다.
이 과제는 가장 늦게 처리하려면 3일에 처리해야되는데 3일은 이미 (40,4)과제가 배정돼있다.
그러니까 그 전날인 2일을 본다. 근데 2일도 (50,2)과제가 배정돼 있다.
그래서 그 전날인 1일을 보고 없으니 배정한다.

그 다음 (20,1)을 가져온다.
이 과제는 1일에 밖에 처리할 수 없는데 1일은 벌써 (30,3)과제를 처리하는 데 써버렸다.
그러니까 넣지 않는다.

....

이렇게 진행된다.

다른 사람의 풀이

1. 마지막 날짜부터 1일차까지 최대한 높은 과제부터 진행

import sys
input = sys.stdin.readline
 
n = int(input()) # 과제수 입력
hw = [list(map(int, input().split())) for _ in range(n)] # 과제기한, 점수 입력
 
hw.sort() # 일수가 가장 큰 순서대로 정렬함
canHW = [] # 해당 일수에 가능한 과제를 저장할 리스트
result = 0
 
# 마지막 일수부터 가장 처음 일수까지 반복
for date in range(n, 0,-1):
    while hw and hw[-1][0] >= date: # 해당 날짜에 수행할 수 있는 과제점수를 리스트에 저장
        canHW.append(hw.pop()[1])
    # 해당 날짜에 수행할 수 있는 과제가 있다면
    if canHW:
        canHW.sort() # 가장 큰 점수대로 정렬함
        result += canHW.pop() # 가장 큰 점수를 pop연산 수행 후 결과에 더함
print(result)

문제의 예시를 보고 설명하면

6일차에는 [6, 5] 밖에 처리를 못한다.
그러니까 이 과제를 처리한다.

5일차에는 마감일이 5일 이상인 과제가 없으므로 수행할 수 있는 과제가 없다.

4일 차에는 [4, 60], [4, 40], [4, 10]가 가능하다.
여기서 sort를 해서 점수가 가장 높은 [4,60]을 얻고, 처리한다.

3일차 => [4, 40], [4, 10], [3, 30]
2일차 => [4, 10], [3, 30], [2, 50]
1일차 => [4, 10], [3, 30], [1, 20]

이런 식으로 진행하는 방법이다.
이런 방법으로도 풀 수 있구나 또 배웠다.
하지만 계속 정렬을 해야되기 때문에 시간 복잡도면에서는 손해일 거 같다.

2. 힙큐가 아닌 정렬을 사용

import sys
N = int(sys.stdin.readline())
homeworks = []
visit = [False] * 1001

for _ in range(N):
    d, w = map(int, sys.stdin.readline().split())
    homeworks.append((d, w))

homeworks.sort(key=lambda x: x[1], reverse=True)
answer = 0
for day, worth in homeworks:
    i = day
    # 과제를 할 날짜 탐색
    while i > 0 and visit[i]:
        i -= 1
    # 과제를 할 날짜가 없으면 패스
    if i == 0:
        continue
    else:
        visit[i] = True
        answer += worth

print(answer)