https://www.acmicpc.net/problem/21777
요약
- job scheduler를 수행한 결과가 주어질때, 원래의 job을 출력하는 문제
- job scheduling
- 우선순위 값이 큰 것
- id가 작은 것
접근법
- 출력형식에서 오류가 있어서 헤맴
- 선택한 프로세스 사이즈 출력
- 값의 범위 확인
- 관찰1
- 가장 처음에 선택한 프로세스는 우선순위 값이 가장 클 것임
- 관찰2
- 다음에 선택한 프로세스는 첫번째 선택한 우선순위와 비교해야할 것임
- 앞서 선택한 프로세스와 같은 프로세스면 => 스킵
- 앞서 선택한 프로세스 id < 두번째 선택한 id : 선택이 되었을때의 우선순위는 앞선 우선순위 + 1이어야함
- 앞서 선택한 프로세스 id < 두번째 선택한 id : 앞선 우선순위여야함 (물론 크다고 생각할 수도 있겠지만, 컸으면 앞에 선택이 되었을 것임. 그래서 같아야함)
- 세번째, 네번째에서도 동일한 원리 적용
- 다음에 선택한 프로세스는 첫번째 선택한 우선순위와 비교해야할 것임
- 관찰3
- 선택받지 않았을때 +1처리
- 구간트리를 이용해서 전체 +1처리를 해도 되겠지만...
- turn이 지나면 모든 프로세스는 +1이 되었을 것임 => 현재가 몇번째 턴인지는 알 수 있음
- 다만 선택받은 경우는 +1이 안되었을 것임
- base(=현재턴에서 +1이 되었을 것으로 기대하는 값) - 선택받은 횟수 ==> 우선순위 가중치
- 우선순위 구현
- 현재 프로세스가 선택되었을때 가져야하는 우선순위 - 우선순위 가중치
검증
- 무작위 데이터로 프로세스 생성
- 무작위 데이터로 job scheduling 수행 및 결과 추출
- 무작위 결과를 입력으로 하여 코드 실행
- 코드실행결과를 데이터로 하여 job scheduling 수행 및 결과 추출
- 결과값 비교 및 반복
newbieski