(JAVA) 백준 3079번 : 입국심사 --- [이진탐색]

https://www.acmicpc.net/problem/3079

3079번: 입국심사

 

 

이진 탐색 문제이다.

 

 

중요한 점이 있다면

 

 

심사대가 비었다고 바로 심사받는 것이 아니라, 자율적으로 쉬면서 바로 안가도 된다 는 것이다.

 

 

그렇기 때문에 이진탐색을 사용한다.

 

 

 

  -  정렬된 배열 : 모든 M명이 심사받는 데 걸린 시간 (1초 ~ 심사 최장 시간 * M명 초)

 

  -  구하는 방법 : mid 초 / 각 심사대 심사 시간

        -> mid 초 내에 해당 심사대에서 심사받을 수 있는 최대 인원 수

 

  -  그래서, 이진탐색을 통해 각 심사대 별 최대 인원 수를 더한 값과 M(명) 의 값을 비교한다.

        -> sum(모두 더한 값) >= M : 초과 인원만큼 쉬게 하면 M명을 만족하므로 별도로 mid 값 저장.

        아래 배열 탐색 (high = mid - 1)

        -> sum(모두 더한 값) < M : mid 초 내에는 M명이 절대 심사를 못받는다. 위 배열 탐색 (low = mid + 1)

 

 

여기서 핵심!

 

 

입력 값이 10자리나 되고, 여기서 high(right) , mid , low(left) 값 뿐 아니라

 

sum 과 mid 초 / 각 심사대 심사 시간 또한 int 크기를 넘어갈 수 있기 때문에

 

반드시 전부 long 형으로 진행해야 한다!

**** 심사대 시간은 int 배열로 해도 된다.

 

 

 

 

그 외 별다른 특이사항 없이

 

위 사항과 이진탐색 알고리즘을 사용하면 해결할 수 있어

 

매커니즘을 작성하지 않겠습니다!

 

 

또한, 이해가 되지 않는 부분은 소스코드를 참고하시며

 

댓글로 남겨주시기 바랍니다.

 

 

 

감사합니다!

 

소스코드

---