[백준] 13904번 과제 - 그리디알고리즘 파이썬

 

13904번: 과제

 

문제 접근 방법

- 마감 기한이 있는 문제는 1에서 N까지 순차적으로 풀기보다는 거꾸로 풀기.

참고 : https://steady-coding.tistory.com/321

 

막혔던 부분

1. 어떤 과제를 먼저 할거냐? 

2. 과제를 시작하고 다음 과제는 어떤 기준으로 선택할 거냐?

이러한 문제는 깊이 고민하기보다는 유형을 빠르게 파악해야 한다고 30분 정도 고민하다가 다른 블로그에서 힌트를 얻어야겠다고 생각했다. (합리화...)

 

1일 차 부터 점수가 높은 것 부터 해결하게 되면 기간이 지난 것들이 발생하여 165 점수를 얻게 된다.

1일차 [4 60][2 50][4 40][3 30][1 20][4 10][6 5]

2일 차 [2 50][4 40][3 30][4 10][6 5]

3일 차 [4 40][3 30][4 10][6 5]

4일 차 [4 10][6 5]

5일 차 [6 5]

 

마감일부터 풀면 185를 얻게 된다.

6일 차 [6, 5]

5일 차 X

4일 차 [4, 60], [4, 40], [4, 10]

3일 차 [4, 40], [4, 10], [3, 30]

2일 차 [4, 10], [3, 30], [2, 50]

1일 차 [4, 10], [3, 30], [1, 20]

 

제출 코드

N = int(input())
hw = [tuple(map(int, input().split())) for _ in range(N)]  # 리스트 보다 튜플이 빠르다 하지만 수정 불가.
sorted_hw = sorted(hw, key=lambda x:x[0], reverse=True) # 튜플 첫번째 인자로 내림차순
total = 0
copy_hw = sorted_hw.copy()
for i in range(N, 0, -1):
  search_hw = [item for item in copy_hw if item[0] >= i]   # n: 4 60, 4 40....   i: 6, 5, ... 과제 마감일 기준 크거나 같은 과제를 모두 찾는다.
  if len(search_hw) !=0: # 과제 마감일 기준 해야할 과제가 있다면
    max_score = max(search_hw, key=lambda x:x[1])  # 가장 점수가 높은 것을 찾는다. 
    total += max_score[1]
    copy_hw.pop(copy_hw.index(max_score)) # 가장 점수 높은 것을 리스트에서 삭제 한다.
print(total)

이렇게 풀었지만 다른 블로그에서 우선순위 큐를 써라고 나와있어서 자료구조를 한번 이용해보고 싶어서 heapq를 사용하여 구현해 보았다. 

 

제출 코드 (max heap)

import heapq
N = int(input())
hq = []
max_day = 0
for i in range(N):
  day, score = map(int, input().split())
  heapq.heappush(hq, (-score, day))
  if max_day < day:
    max_day = day
assigned = [False] * (max_day + 1)
total = 0
while hq:
  score, day = heapq.heappop(hq)
  print(score, day)
  score = -score
  for i in range(day, 0, -1):
    if assigned[i]:
      continue
    assigned[i] = True
    total += score
    break
print(total)

최대 힙 구조는 아마 다른 곳에서 서치를 하면 개념과 사용방법에 대해 나올 것이다. 아래와 같은 규칙을 갖고 알고리즘을 풀어나갔다.

1. 점수가 높은 순으로 해결한다.

2. 해당 일자에 할 일이 있으면 우선순위를 뒤로 한다.

 

먼저 루트 노드를 기준으로 높은 점수부터 낮은 점수까지 아래와 같이 트리를 만든다.

[4 60]

[2 50]              [4 40]

[3 30] [1 20]         [4 10] [6 5]

 

이후 하루에 한 개의 과제를 할 수 있으니 [False, False, False, False, False, False] 6칸을 만든다.

맨 처음 [4 60] 뽑고 4일 차에 넣는다.  [False, False, False, True, False, False] 

이후 똑같은 방법으로 계속 넣게 되는데 [4 40] 은 이미 4일차에 True가 되었기 때문에 넣질 못하고 4보다 이하이면서 비어있는 3에 넣는다. 이런 식으로 반복하면 아래와 같이 채워지게 된다.

 

[False, False, False, [4 60], False, False]

[False, [2 50], False, [4 60], False, False] 

[False, [2 50], [4 40], [4 60], False, False] 

[[3 30] , [2 50], [4 40], [4 60], False, False] 

[[3 30] , [2 50], [4 40], [4 60], False, [6 5]] 

 

 

제출코드 (min heap)

import heapq

hw = []
N = int(input())
for i in range(0, N):
  deadline, score = map(int, input().split())
  hw.append((deadline, score))
hw = sorted(hw, key = lambda x: x[0])  # 데드라인 오름차순 1 2 3 4...
score_heap = []
for h in hw:
  heapq.heappush(score_heap, h[1])   # 무조건 힙에 점수를 넣는다.
  if len(score_heap) > h[0]:   # 현재 n일 차인데 데드라인이 이미 지난경우
    heapq.heappop(score_heap)  # minheap이기 때문에 가장 작은 점수를 빼준다.
print(sum(score_heap))

앞에서는 데드라인 내림차순으로 진행하였고 다른 코드를 뒤져보다가 오름차순으로 하는 방법이 있었다. 아래 방법대로 무조건 점수를 minheap 자료구조에 넣고 데드라인이 지나면 현재 상태에서의 최소 점수를 heap에서 빼준다. 4일 차가 3번이고 4 40이 들어왔을 때 점수 10을 빼고 4 60이 들어왔을 때 점수 20을 빼준다.

 

 

 

 

결과는 모두 성공!! 힙 자료구조를 사용하니깐 시간이 확실히 줄어들었지만 메모리 사용량이 올라갔다. 힙 구조가 빠르다는 건 알고 있었는데 실제로 눈으로 확인해 볼 수 있어서 좋았다. 그리고 가장 마지막에 한 minheap은 시간 복잡도가 O(N)이라 가장 빠를 것 같았지만 이문제에서는 80ms로 maxheap과 동일했다. 하지만 이후 문제에서는 빠른 것을 확인할 수 있다.

 

아래는 비슷한 유형의 문제이다.

[백준] 1781번 컵라면 - 그리디알고리즘 파이썬