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를 이용하는 방법도 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 2623 음악 프로그램 (0) | 2021.06.06 |
|---|---|
| [BOJ/백준] 1338 알 수 없는 번호 (0) | 2021.06.06 |
| [BOJ/백준] 21777 리버스 가희와 프로세스 (0) | 2021.06.05 |
| [BOJ/백준] 21776 가희의 읽기 쓰기 놀이 (0) | 2021.06.05 |
| [BOJ/백준] 21775 가희와 자원 놀이 (0) | 2021.06.02 |