백준_21773_가희와 프로세스 1(python)

★ 접근법

 문제에서 우선순위가 높은 프로세스 기준 프로세스가 같다면 id가 작은 것이 우선이라고 했을 때 => 우선순위, 최대 십만크기 바로 heapq를 떠올렸다. 

★ 풀이법

 나머지 프로세스의 우선순위를 1 증가시키는 방법만 떠올린다면 말도 안되게 쉬운 문제이다.

그대로 구현하면 최대 백만 초 * 최대 십만 개의 프로세스이기 때문에 시간초과가 발생한다.

나머지 프로세스의 우선순위를 1 증가시키는 것이 아닌 자신의 프로세스를 1 감소시키는 것이다. 우선순위는 상대적이기 때문에 나의 우선순위를 1 감소시키면 자연스럽게 나머지 프로세스의 우선순위가 1 증가된 것처럼 보인다.

 

- 코드

import sys,heapq
input = sys.stdin.readline
t,n = map(int,input().split())
data = []
for _ in range(n):
    a,b,c = map(int,input().split())
    heapq.heappush(data,[-c,a,b])

for _ in range(t):
    cc, ca, cb = heapq.heappop(data)
    cc = -cc # 생각하기 쉽게 잠시 양수로
    print(ca)
    if cb -1 > 0:
        heapq.heappush(data,[-cc+1, ca , cb - 1])

★ 회고

 도대체 어떻게 시간 안에 나머지 프로세스의 우선순위를 1씩 증가시키라는 것인가!!를 한 시간 정도 생각했다. 생각하다가 내가 썼던 티스토리 글들을 보고 있었는데 우연히 이 글이 눈에 들어왔다.

https://cochin-man.tistory.com/28

백준_6198_옥상 정원 꾸미기(python)

이 글에서 내가 바라보는 옥상의 아닌!! 나를 바라보는 옥상!!, 생각의 전환!!을 보게 됐다.

생각의 전환이라는 키워드를 보고 1을 감소해보기로 했다!

다음부터는 생각의 전환을 바로바로 떠올려보자!!