[BOJ] 17612

less than 1 minute read

쇼핑몰

17612번 https://www.acmicpc.net/problem/17612

KOI(한국정보올림피아드) 2019 1차대회 문제입니다.

줄을 세울 때와 빠져나올 때 각각의 경우에 대한 priority_queue를 사용했습니다.

줄을 세울 때 {id, top의 시간 + w, 계산대 번호} 를 데이터로 사용해 그 사람의 계산이 끝나는 시간을 저장해줬습니다.
계산이 끝나는 시간이 같다면 카운터 번호가 낮은 순으로,
그렇지 않다면 먼저 계산이 끝나는 게 top으로 오도록 했습니다.

빠져나올 때에는 줄을 세울 때 이용했던 pq에서 데이터를 빼와서
계산이 끝나는 시간이 같다면 카운터 번호가 높은 순으로,
그렇지 않다면 먼저 계산이 끝나는 게 top으로 오도록 했습니다.

이제 빠져나올 때를 다룰 때 사용했던 pq에는
먼저 빠져나오는 사람이 top에 가까이 있도록 정렬되어있으므로 pop을 해주며 계산해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/17612.cpp

Categories:

Updated:

Leave a comment