[백준] 13094 과제 | Gol3 | 힙 Python

[백준] 13094 과제 | Gol3 | 힙 Python

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

 

 

구상

• 풀이 1 : 별다른 자료구조 사용않고 그냥 구현함 (112ms)
  로직 특성상 힙을 활용한 방식보다 느리다.
• 풀이 2 : 힙 (56ms)
  이 방식이 속도가 훨씬 빠르다!
  접근 방식을 아예 다르게 해야 힙을 쓸 수 있었다. 로직을 새로 짬. 더 효율적인 로직임!

 

[문제 해석]

• 얻을 수 있는 점수 최댓값 구하기
• 과제는 하루에 1개만, 완료 시 점수
• 과제 별로 점수 다름. 마감일 지나면 점수x
• 과제 개수N <= 1,000 : 오 얼마 안되네?
• 마감일까지 남은 일수d <= 1,000
• 시간 제한 : 1초

 

구상 - 힙 쓰는 ver

• 과제를 점수 큰 순으로 마감일에 가장 가까우면서 배치가능한 자리에 배치
• 구현
  • 과제 점수 기준으로 최대힙을 만든다.
  • 점수가 가장 큰 과제부터 힙에서 pop하며 해당 과제 마감일에 배치해본다.
  • 해당 날짜에 이미 배치가 되어있으면 배치 가능한 날짜 중 마감일 이전 가장 늦은 날짜에 배치한다. 

=> 이러면 어차피 점수가 큰 순이라 최적이 된다!

무조건 점수 큰 걸 먼저 배치해야 유리하니까.. 오.. 나는 생각 못한 방식이다

 

 

구상 - 그냥 구현 ver

• 과제를 마지막날부터 거꾸로 돌면서 배치하면 될 것 같다.
• 구현
  • 과제를 점수가 큰것부터 정렬
  • 날짜를 거꾸로 돌면서, 해당 날짜에 마감일이 아직 지나지 않은 과제 중 가장 점수가 높은 과제를 해당 날짜에 배치
    이 부분 구현 방법 생각나는 거 2가지
    1. 점수 기준으로 정렬하고, 점수 제일 큰 과제에서부터 날짜가 지났는지 확인. 날짜가 안지난 게 나오면 바로 pop (리스트pop이라 시간많이 걸릴듯)
    2. 날짜 기준으로 정렬하고, 날짜가 아직 안지난 과제까지만 돌면서 점수들 중 최대값 갱신하면서 구함
       • 2번 방식은 최악의 경우 nlogn + d*n = d*n (n^2) 인데 최악이라도 n, d가 1000밖에 안돼서 1000^2 = 10*6 < 10^8 이라 괜찮을 거 같은... 해볼까
          -> 이걸로 풀었는데 성공했다. 힙 쓰는 풀이도 찾아봐야지
         
         

 

트러블 슈팅

• 인덱스 -1로 초기화할 때 나중에 예외처리 항상 까먹지 않게 주의하기..~~~

 

코드 - 힙 (빠름)

# v2 : 힙 (56ms)
#이 방식이 속도가 훨씬 빠르다!
#접근 방식을 아예 다르게 해야 힙을 쓸 수 있었다. 로직을 새로 짬. 더 효율적인 로직임!

'''
[문제 해석]
- 얻을 수 있는 점수 최댓값 구하기
- 과제는 하루에 1개만, 완료 시 점수
- 과제 별로 점수 다름. 마감일 지나면 점수x
- 과제 개수N <= 1,000 : 오 얼마 안되네?
- 마감일까지 남은 일수d <= 1,000
- 시간 제한 : 1초

구상 (힙 쓰는 ver)
- 과제 점수 기준으로 최대힙을 만든다.
- 점수가 가장 큰 과제부터 힙에서 pop하며 해당 과제 마감일에 배치해본다.
- 해당 날짜에 이미 배치가 되어있으면 배치 가능한 날짜 중 마감일 이전 가장 늦은 날짜에 배치한다. 
이러면 어차피 점수가 큰 순이라 최적이 된다! 무조건 점수 큰 걸 먼저 배치해야 유리하니까.. 오.. 나는 생각 못한 방식이다
'''

import heapq
import sys
input = sys.stdin.readline

N = int(input())
works = []
max_day = 0
for _ in range(N) :
    day, score = map(int, input().split())
    works.append((-1*score, day)) #heapq를 최대힙으로 쓰기위해 음수로 저장

    max_day = max(max_day, day) #가장 늦은 마감일 저장

heapq.heapify(works)

score_arr = [0]*(max_day+1)
while works :
    score, deadline = heapq.heappop(works) #가장 점수가 높은 과제
    score *= -1 
    # print(deadline, score)
    for day in range(deadline, 0, -1) :
        # print(day)
        if score_arr[day] == 0 :
            # print("set")
            score_arr[day] = score
            break

# print(score_arr)
print(sum(score_arr))

 

코드 - 딱히 자료구조 쓰지 않고 그냥 구현 (느림)

# v1 : 별다른 자료구조 사용않고 그냥 구현함 (112ms)
#로직 특성상 힙을 활용한 방식보다 느리다.
# TS : 인덱스 -1로 초기화할 때 나중에 예외처리 항상 까먹지 않게 주의하기..~~~

'''
[문제 해석]
- 얻을 수 있는 점수 최댓값 구하기
- 과제는 하루에 1개만, 완료 시 점수
- 과제 별로 점수 다름. 마감일 지나면 점수x
- 과제 개수N <= 1,000 : 오 얼마 안되네?
- 마감일까지 남은 일수d <= 1,000
- 시간 제한 : 1초

구상
- 과제를 마지막날부터 거꾸로 돌면서 배치하면 될 것 같다.
- 구현
    - 과제를 점수가 큰것부터 정렬
    - 날짜를 거꾸로 돌면서, 해당 날짜에 마감일이 아직 지나지 않은 과제 중 가장 점수가 높은 과제를 해당 날짜에 배치
        - 이 부분 구현 방법 생각나는 거 2가지
            1. 점수 기준으로 정렬하고, 점수 제일 큰 과제에서부터 날짜가 지났는지 확인. 날짜가 안지난 게 나오면 바로 pop (리스트pop이라 시간많이 걸릴듯)
            2. 날짜 기준으로 정렬하고, 날짜가 아직 안지난 과제까지만 돌면서 점수들 중 최대값 갱신하면서 구함
                - 최악의 경우 nlogn + d*n = d*n (n^2) 인데 최악이라도 n, d가 1000밖에 안돼서 1000^2 = 10*6 < 10^8 이라 괜찮을 거 같은... 해볼까
                -> 이걸로 풀었는데 성공했다. 힙 쓰는 풀이도 찾아봐야지
'''


import sys
input = sys.stdin.readline

N = int(input())
works = [tuple(map(int, input().split())) for _ in range(N)]
done = [False]*N

works.sort(reverse=True) # 튜플 첫번째 값인 날짜가 큰 기준으로 정렬됨

score_sum = 0
for day in range(works[0][0], 0, -1) : #가장 큰 마감일부터 날짜를 돈다

    score_max_idx = -1
    score_max = 0
    for i in range(len(works)) :
        deadline, score = works[i]

        #마감일 지난 과제가 나왔으면 이번 날짜 탐색 중지
        if deadline < day :
            break
        #이미 한 과제면 넘어감
        if done[i] :
            continue
        
        #점수 더 높은 과제가 나왔으면 갱신. 이때 점수가 동일해도 마감일이 늦은 걸 골라야 유리하므로 등호 미포함
        if score_max < score :
            score_max_idx = i
            score_max = score


    #아무 과제도 선택되지 않았으면 넘어감 # TS
    if score_max_idx == -1 :
        continue

    #최종적으로 이 날짜에 선택된 과제 완료 처리, 점수 증가
    done[score_max_idx] = True
    score_sum += score_max

print(score_sum)