[백준][이분탐색] 3079번 입국검사

문제

총 M명의 사람이 최소한의 시간으로 N개의 입국심사대를 통과해야할 때 최소한의 시간을 구하시오. 

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/3079), 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/43238)

풀이

이분탐색으로 푸는 문제입니다. 처음에는 무슨 방법으로 풀어야하지? 생각이 들었는데 최소한의 시간을 구하기 위해 최대한의 범위를 잡은 다음, 그 범위 안에 M명의 사람이 심사가 가능하다면 시간을 줄여가고 가능하지 않다면 시간을 늘려가며 구할 수 있겠다는 생각이들었습니다. 이분탐색의 개념은 다른 문제와 비슷하게 low, mid, high를 통해 그대로 구현하면 되지만 여기선 값이 너무 큰 탓에 최대값을 정하는 데 어려움이 있었습니다. 사실 어려움은 아니고 모두 long long 타입으로 바꾸어주었는데도 오버플로우때문에 생기는 부분이 어딘지를 찾는데 시간이 걸렸습니다. 백준, 프로그래머스 둘 다 같은 문제인데 프로그래머스의 경우에는 input이 type이 정해져서 들어오는데 int형으로 들어오는 input을 통해 곱하기 연산을 할때 (long long)을 통해 명시적으로 type casting을 안해줘서 생긴 문제였습니다. 이분탐색에서는 최대값을 잡는게 중요하다 생각했는데 저는 가장 오래걸리는 심사시간*M 을 통해서 최대값을 정해주었습니다!

코드

https://github.com/kswim/Algorithm/blob/master/BinarySearch/3079.cpp