[BOJ 13904, Python 3] 과제

https://www.acmicpc.net/problem/13904

13904번: 과제

 

 

순회강연 문제랑 범위만 다르고 똑같습니다.

순회강연보다 N범위가 작아서 아무거나 해도 시간 차이가 별로 나지 않습니다.

 

풀이 1

점수를 기준으로 내림차순으로 정렬하고, 1일부터 x일까지 예약을 확인할 수 있을지 확인해볼 것이니 최대 1000일까지 확인할 수 있으므로 visit 배열의 크기를 1001로 해줍니다.

내림차순한 배열을 for문으로 돌리면서 1일~x일에 예약을 할 수 있는지 for문으로 확인해봅시다. 예약할 수 있으면 하고, 아니면 넘어갑니다.

N = 1000이라서 O(N^2)가 돌아가고도 남습니다.

 

코드 1

n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)], key=lambda x: -x[1])
ans = 0
visit = [0] * 1001
for day, val in arr:
    for i in range(day, 0, -1):
        if not visit[i]:
            visit[i] = 1
            ans += val
            break
print(ans)

 

풀이 2

이번엔 기한을 기준으로 오름차순 정렬을 합니다.

그리고 최소힙을 이용해서 값을 추가하다가 (최소힙에 들어있는 원소의 개수) > (현재 인덱스가 가지고 있는 기한)일 경우 하나를 빼서 값을 같게 해야하기 때문에 제일 적게 점수를 얻는 원소를 버리면 됩니다.

 

풀이 1은 점수를 내림차순하여 가장 큰 점수를 가진 것부터 확인하고, 풀이 2는 최소힙을 이용하여 힙에 값을 저장하다가 가장 작은 점수를 버리게 하는 것으로 과정만 살짝 다를 뿐이지 전부 최대 점수를 취하려고 하는 과정이라 결과는 같습니다.

 

코드 2

from heapq import *
n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)])
ans = []
for i in range(n):
    heappush(ans, arr[i][1])
    if len(ans) > arr[i][0]:
        heappop(ans)
print(sum(ans))