[C++] 입국심사

[문제]

코딩테스트 연습 - 입국심사 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

문제에서는

처럼 나와 있기에 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;
}