BOJ 3079 - 입국심사
얼핏봐서는 이분 탐색으로 보이지 않는 문제인데, 잘 생각해보면 이분 탐색이 맞아서 신기한 문제였다.
‘이 값도 가능한가? 그럼 이거는 가능해?’ 하면서 범위를 좁혀나가는 것이기 때문에 무엇을 타겟으로 잡을지 잘 정해줘야 고생하지 않는다.
내 개인적으로 정리해보는 차원에서 이번 문제는 접근 방법을 조금 자세히 써보려고 한다.
접근 방법
문제를 잘 읽어보고, 예시로 주어진 내용을 직접 계산해보자.
각 심사대에 3명씩 가는 경우 : 7 x 3 = 21, 10 x 3 = 30, [21 < 30] -> answer : 30
짧은 심사대에 4명이 가는 경우 : 7 x 4 = 28, 10 x 2 = 20, [28 > 20] -> answer : 28
당연한 얘기겠지만.. 모든 심사대에 동일한 인원이 줄을 서는게 최선이 아니라는 점.
`한 심사대에서 심사에 사용한 시간의 최대값’을 가장 작게 하는 값을 찾으면 된다.
그럼 이런식으로 의사 코드를 생각해볼 수 있겠다.
n = 심사대 갯수
count = (심사 받아야할 인원수)
index = (현재 심사대 번호)
min, max = (이분 탐색에 사용할 최소 / 최대값)
mid = (각 심사대에서 심사로 사용할 수 있는 시간 비용)
desk[] = (심사대별 소요시간 배열)
while(min < max) {
mid = (min + max) / 2
while(count가 0이 되거나 심사대 번호가 끝에 도달할 때까지)
count에서 (mid / desk[index]) 만큼 감소
if(반복문을 벗어날 때까지 count가 0에 도달하지 못했다면)
min = mid+1
else(count가 0에 도달했다면)
max = mid
}
min은 mid+1인데, max에 mid를 넣는 이유는.. 그 값이 정답일 수도 있는 값이기 때문이다.
예를 들어서 27까지는 불가능한 값이고 28이 정답인데, 28이 max인 상태에서 이분 탐색이 계속 돌아간다면 이걸 계속 포함시켜줘야 불상사가 일어나지 않을 것이다.
특별히 주의해야할 점이 있다면 m제한과 Tk 제한이 10억이기 때문에 long을 꼭 써줘야 한다는 것!