• 떡볶이 떡 만들기와 동일한 유형이다.
• 최소한의 조건을 맞추라는 문제가 나왔을때 이렇게 접근하자.

최소값을 구하는 부분이다. - 최근

• 타겟값이 어떤값인지 모르는 상황에서 시작하므로
  
  -> 구하고자 하는 answer를 가장 높은값으로 설정한 후에 진행하자.

위의 예처럼 (7,10) 이고 mid값이 30, n = 6 (n은 검사받아야 할 모든 인원수)이라면
계산결과값이 : (30 / 7) + (30 / 10) = 7이 나온다.
7이 최소값인지는 단정지을 수 없으므로 계속 진행해야 한다는 것을 유추할수 있다.
여기서 first 를 mid -1로 할까? end를 mid +1 로 갱신할까 생각이 가능하다.
여기서 n이 의미하는 것은 검사받아야할 모든 인원수 -> 이것과 비교를 할 수 있다.
result값이 7이라는 것은 30분이라는 시간 동안 (7, 10)의 사람이 7사람을 검사 완료하는데 걸리는 시간을 나타내는 것이다.
result 와 n을 비교하자. result와 n이 동일하다면 최적의 조건에 근접하다 라는 것을
생각할 수 있다.
그렇다면 조건 식을 if(result > n) 일 때 end = mid - 1; 이라고 생각할수 있다.
result값을 줄여야 하므로.
그러면 if(result < n) 은 first = mid + 1;
if(result == n ) 일때 종료 시켜야 하는 것인가?
29를 (7,10) 진행하면 result 는 6이 나온다.
28를 (7,10) 진행하면 result 는 6이 나오는 것을 생각할 수 있다.
이를 통해 if(result >= n ) 동일하게 묶어야 한다. 그리고 이때 출력값을 갱신해야 한다.
if(result < n)일때 출력을 갱신할 필요가 없는 이유는
mid를 15로 해서 (7,10) 진행하면 result 는 3이 나오는데 , 완료된 사람이 3명 밖에 없다! n은 6명, 즉 완료해야할 사람이 6명인데 mid가 15이면 6명을 충족하지 못하다는 것을 의미하므로! if(result < n)은 출력값을 갱신할 필요 없다

주의할 점.

-> 자료형이 달라서 테스트 케이스 1개 통과 못한다.
자료형을 동일하게 맞춰서 진행하자.

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    
    sort(times.begin(), times.end());
    
    
    long long first = 0;
    long long end = times.back() * (long long)n;
    long long answer = end;
    
    while(first <= end)
    {
        long long mid = (first + end) / 2;
        
        long long sum = 0;
        for(int i = 0; i < times.size(); i++)
        {
            sum += mid / times[i];
        }
        
        if(sum >= n)
        {
            end = mid - 1;
            answer = min(mid, answer);
        }
        else if(sum < n)
        {
            first = mid + 1;
        }
        
        
    }
    
    
    
    return answer;
}

중요한 부분 - 옛날 생각

문제에서는 최소값을 구하는 것이다. 반드시 target값보다는 크거나 같아야 한다.
만약에 sum과 target이 딱 맞게 떨어지지 않을 수도 있다.

따라서 이렇게 변경해야 한다.

• 중요한 조건.
  
  target보다는 커야하므로 result값을 갱신할수 있다.
  //모든 사람들이 모두 입국 심사를 거쳐야 하므로! 여기서
  모든 사람들은 target이다.
  여기서는 target : 6이다. 즉 6명의 사람들이 모두 임국 심사를 받아야 하므로
  6이상의 사람들만 최적의 값을 갱신하면된다는 것이다.
  target보다 작다면 값을 갱신할 필요가 없으므로 sum < target은
  값 갱신하지않고, 이진탐색만 진행중인 것이다.
  그리고 이분탐색이 진행할 수록 값이 최적화되고,
  내가 미리 윗단에서 조건을 주었기 때문에 자동으로 반복문이 종료된다.
  그러므로 강제적으로 종료조건에 대해서 정의할 필요는 없다.