처럼 나와 있기에 n을 찾아서 answer(return) 값을 찾는 것처럼 나와있지만 반대로 answer이 될 부분을 1 ~ 100,000,000,000(대충 큰 숫자) 에서 n이 나올 수 있는지를 파악해보자.
즉, 문제의 예시에서 28의 경우라면 28 / 7 => 4 와 28 / 10 => 2 가 합쳐지면 6이 나온다.
반대로 만약 30이라면 30 / 7 => 4 와 30 / 10 => 3이 더해져서 7이 나오니 우리는 주어진 n보다 큰 수가 나오니 이분탐색을 이용해서 해당 값을 더 줄일 수가 있다.
설명에서는 대충 큰 수라고 했지만 코드에서는 times에서 가장 큰수 * n을 작성하였다.
[회고]
이진탐색이 이루어지는 필수조건은 sort가 되어있다는 전제하에서 이루어진다.
그런데 문제를 풀다가 계속해서 해당 부분을
times = timesh;
sort(times.begin(),times.end());
로 써야 하는데
sort(times.begin(),times.end());
times = timesh;
위와 같이 써서 계속해서 틀렸었다. 코드를 쓸때 유의하도록 하자...
[코드]
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> times;
long long parametric(long long n){
long long answer = 0;
for(int i = 0;i<times.size();i++){
answer += n / times[i];
}
return answer;
}
long long solution(int num, vector<int> timesh) {
long long answer = 0;
times = timesh;
sort(times.begin(),times.end());
long long n;
n = num;
long long start = 1;
long long end = n * times[times.size() - 1];
long long mid = 0;
while(start <= end){
mid = (start + end) / 2;
if(parametric(mid) >= n){
end = mid - 1;
}
else {
start = mid + 1;
answer = start;
}
}
return answer;
}