https://www.acmicpc.net/problem/21778
요약
- 스케쥴링에 따라 프로세스를 실행
- 우선순위 큰 것, 아이디 작은 것
- Tc번째에 선택되는 프로세스 찾기
- Tc의 값이 크기때문에 완전탐색으로는 안됨
- 아이디어 떠오르기 힘들었는데 티어도 생각보다 많이 낮고, 티어 의견들도 간단해서 당황스럽다 ㅠㅠ
접근법 - 실패
- 특정 시점에서 가장 큰 값의 우선순위가 무엇일까를 생각함
- 프로세스들은 시간이 지나면서 +1씩 우선순위가 증가하거나
- 처리가 되면서 시간이 줄기때문에
- 목표가 되는 우선순위를 알면 얼만큼 처리가 되었는지 알 것임
- x의 시간이 흘렀고 +x를 했을때 목표보다 넘으면 : 넘는 만큼은 처리가 되었을 것임
- +x를 해도 목표를 못넘으면 : 처리가 안되었을 것임
- 뭔가 논리적인 빈틈이 보이지만 일단 진행해봄
- Tc시간 바로 전에 해당하는 목표 우선순위를 구했다고 쳤을때
- 목표 우선순위를 만족하기 위해 각각의 프로세스가 대략 어떻게 동작했는지를 구해보고
- 시간을 흘려서 Tc - 1까지 동작시킨 후에
- 한번 더 동작시켰을때 선택한 프로세스가 구하려고 하는 값일 것임
- 목표 우선순위는 이분탐색으로 구하지 않을까... 생각했었음
- 빈틈들
- 목표우선순위가 증가만 하지는 않음 : 큰 값을 갖는 프로세스가 처리가 끝나면 남는 것들로 인해 목표우선순위가 감소할 수 있음
- 목표 우선순위를 찾기 위한 이분탐색이 적절하지가 않음
- 작업 시간 기준으로 찾아보려고 해도 작업시간이 크고, 작고 변화를 이용하기가 어려움
접근법 - 성공
- 프로세스 처리할때 모두가 +1되는 처리를 선택받은 프로세스만 -1하는 처리로 구현했었음(가희와 프로세스 1 문제)
- 이런 생각을 해볼 수 있음
- 가장 큰 우선순위 프로세스는 어쨌든 선택받고 -1이 될 것임
- 이후로도 큰 우선순위를 갖는 것들은 선택받고 -1이 될 것임
- 이런식으로 뾰족한 것들(큰 우선순위를 갖는 것들)은 -1씩 깎여 나갈 것임. 마치 산봉우리를 깎아서 평지를 만들어 나가는 것처럼...
- tc-1시점 근처의 목표 우선순위를 구한다고 할 때
- 각각의 프로세스는 목표우선순위가 아예 될 수 없거나(애초에 작아서)
- 목표 우선순위가 되기위해 m번 선택을 받았을 것임(물론 주어진 실행시간보다 더 클 수도 있음 m이). 어쨌든 깎이고 깎여서 목표 우선순위로 평평해 지는 시점은 발생할 것이므로
- 이때 선택받은 것들의 합 = 전체 수행 시간일 것임 : 어떤순서인지는 모르지만 각각의 프로세스들이 선택된 합은 알게 되니까
- 그리고 이 값이 tc-1보다 작거나 같으면서 가장 작은 값은 구할 수 있을 것임. 이분탐색으로.
- 그때의 프로세스들의 상태를 구한 후 tc-1이 될때까지 프로세스들을 흘림 = 시뮬레이션함 = 많아야 n개일 것임(우선순위가 1작아지는데 걸리는 최대 시간이 모든 프로세스들을 다 선택하는 수이므로)
- 그리고 한번 더 스케쥴링을 진행하면 구하고자 하는 답임
- 예를 들어 30일때의 값을 구하고 싶으면 29번 스케쥴링을 수행했을때의 상태를 구하고, 한번 더 수행하면서 값을 구하면 됨
newbieski