모든 인원을 심사하는데 걸리는 최소 시간과 최대 시간을 가정한 뒤, 그 값들을 이용하여 시간을 계산해볼 수 있다.
가장 적게 걸리는 시간은 1, 가장 많이 걸리는 시간은 times배열의 가장큰 값에 n을 곱한 값이다.
처음에는 가장 적게 걸리는 시간을 n명의 인원 * 1분의 심사시간인 n으로 책정하고 문제를 풀었는데, 디버그 과정에서 이는 심사관이 1명일 때의 가정임을 깨닫고 최소시간을 1로 수정하였다.
코드를 작성하고 제출했는데 몇 케이스에서 오답이 나와서 고민하다가 질문 게시판을 봤더니, long long을 넘는 오버플로가 발생하는 경우가 있다고 한다.
(참고 링크: https://school.programmers.co.kr/questions/43465)
long long을 unsigned long long으로 변경해서 제출하니 정답이 나왔다.
주어진 값 안에서 하는 이분탐색이 아닌 가능한 시간의 최대와 최소를 이용하여 푸는 문제라 접근이 쉽지 않았는데 타입까지 신경써야하는 문제였다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
unsigned long long solution(int n, vector<int> times) {
unsigned long long answer = 0;
sort(times.begin(), times.end());
unsigned long long l = 1; // 모든 사람을 처리하는데 걸리는 최소 시간
unsigned long long r = times.back() * n; // 모든 사람을 처리하는데 걸리는 최대 시간
while(l <= r){
unsigned long long mid = (l+r)/2; // 모든 사람을 처리하는데 걸리는 평균 시간
unsigned long long cnt = 0;
for(int i: times){
cnt += mid/i; // 평균 시간동안 처리할 수 있는 사람의 수
}
if(cnt >= n){ // 처리가능한 사람의 수가 기다리는 사람의 수보다 많음 -> 처리 시간이 줄어드는 경우도 탐색
if(answer == 0){
answer = mid;
} else{
answer = min(answer, mid);
}
r = mid - 1;
} else{ // 처리가능한 사람의 수가 기다리는 사람의 수보다 적음 -> 처리 시간을 늘려야함
l = mid + 1;
}
}
return answer;
}