[BOJ/백준] 21778 가희와 프로세스 2

import sys
input = sys.stdin.readline
INF = (10**12)+1

def get_process(mid_priority):
    global N
    if dp.get(mid_priority):
        return dp[mid_priority]
    else:
        total_process_cnt = 0


        for i in range(N):
            process = arr[i]

            if mid_priority<=process.sp:
                total_process_cnt += process.time
            elif process.sp< mid_priority<=process.ep:
                total_process_cnt = total_process_cnt + process.ep - mid_priority +1
        
        dp[mid_priority] = total_process_cnt
        return total_process_cnt


def b_search(target_T):
    left = 0
    right = INF*2
    while left<=right:
        mid = (left+right)//2
        total_cnt = get_process(mid)
        if total_cnt>=target_T:
            next_priority_cnt = get_process(mid+1)
            if next_priority_cnt<target_T:
                remain_priority_cnt = target_T - next_priority_cnt
                for i in range(N):
                    if arr[i].sp <= mid <=arr[i].ep:
                        remain_priority_cnt -= 1
                        if remain_priority_cnt == 0:
                            result.append(arr[i].process_id)
                            break
                break
            else:
                left = mid + 1

        else:
            right = mid-1


class Process:
    def __init__(self,_id,_spend_time,_init_priority):
        self.process_id = _id
        self.time = _spend_time
        self.ep = _init_priority+INF
        self.sp = _init_priority+INF-spend_time+1


Q,N = map(int,input().split())
arr = []
for _ in range(N):
    process_id,spend_time,init_priority = map(int,input().split())
    new_process = Process(process_id,spend_time,init_priority)
    arr.append(new_process)
dp = {}
arr.sort(key=lambda x : x.process_id)
result = []

for _ in range(Q):
    find_time = int(input())

    b_search(find_time)


for i in range(Q):
    sys.stdout.write(str(result[i])+'\n')

 

 

이 문제 또한 앞선 문제와 같이 혼자서 풀기 어려운 난이도라, https://github.com/cdog-gh/gh_coding_test 해설을 보고 푼 문제이다.

 

이 문제는 boj.kr/21773 과 boj.kr/21777 문제를 이해해야지만 풀 수 있는 문제였다.

 

앞서 21777에서 말한것처럼  초기 priority가 P라 하고, 총 실행시간이 T라한다면,

 

 

P~ (P-T+1) 까지 우선순위를 실행하게 될 것이다.

 

그러므로 우리는 무지하게 큰 초기값을 각각의 priorty에 더해준다. 왜냐하면, 양수의 priority로만 구분을 해주기 위함이다.

 

 

그러므로 INF + P 를 end_priority 그리고 INF + P - T + 1 를 start_priority 로 해주었다.

 

 

근데 숫자가 커서 end_priority와 start_priority라 했지만, 이 문제를 더 쉽게 이해하기 위해선 반대로 바꾸는것도 한다.

 

왜냐하면 우선순위가 클수록 먼저 실행이 되기 때문이다.

 

그러면 우리는 시간 T를 찾는것이다.

 

시간 T를 찾는 방법은 다음 과 같다. 특정 priority일때까지 실행된 모든 프로세스의 개수를 세주는 것이다.

 

priority가 실행된 개수가 곧 실행시간이기 때문이다.

 

여기서 주의해야할점은 get_process(priority) == T 를 만족하는 priority가 많을 것이다.

 

그러므로, 우리는 priority가 현재보다 1이 커졌을때 T보다 작아지는 경우를 찾아야,

 

구하고자하는 실행시간 T에 실행되는 process를 찾을 수 있다.

 

나머지는 이분탐색처럼 하면 되는데 여기서 주의해야할점은 다음과 같다.

 

 

priority가 높을수록 일찍 실행되고, 낮을수록 늦게 실행된다.

 

만약 K라는 priorty까지 실행되는 priority의 개수를 구해야한다면,

 

K <= start_priority 와 같다면, 이 process_id가 가진 모든 실행시간을 쓴 것이기 때문에 전부 더해주면 된다.

 

그리고 start_priority < K <= end_priority 일때에는

 

end_priority - K + 1까지가 프로세스가 실행된 것이기 때문에 이 부분을 더해주면 된다.

 

 

마지막으로, 우리가 구한 get_process(mid_priority) >= T  와 get_process(mid_priority+1)<T를

 

만족하는 mid_priority에서 실제로 실행된 priority를 구해야한다.

 

get_process(mid_priority)  - get_process(mid_priority+1) 을 빼준값을 remain_priority_cnt라 하고

 

id 1부터 해서 mid_priorty가 해당 프로세스의 start_point와 end_point 사이에 있으면  이 값을 한개씩 줄여주면서 

 

 

0이 되었을때 실제로 실행된 process_id이므로 그때의 process_id를 출력해주면 된다.

 

그리고, get_process에서 특정 process에 대한 total_cnt는 동일할것이기 때문에 캐싱을 해주면 된다.

 

또한 dp테이블로 만든게 아닌, 함수이므로, functools의 lru_cahce를 이용하는 방법도 있다.