260422_문제 풀이 전략

• 경우의 수가 굉장히 많다.
  : 사람 100억명, 심사관은 10만이다. => 불가 .

• 어떤 특정값을 가지고 결론 도출하는 이분탐색으로 진행

초기값 설정 주의할 점.

• 문제 분석할때 위에서 사람 100억명인데 한명 처리하는데 100억분이 있다.
  -> answer와 right를 굉장히 크게 잡아야 한다.
  

초기값에 주의하자.
right와 answer 둘다 동일하다.
: 심사위원의 최대 숫자 처리하는데 걸리는 최대 시간이므로
=> 10만 10억이다.

더 중요한거 : 260714

반드시 초기화값에 l이나 ll을 붙여야 함!
-> 안붙이면 틀린다.

• type 처리.
  
  

---

시간 복잡도

• 1) 최적화할 때 left : 1, right = 10억 10억이고
  -> 이분탐색이므로, log (10억 10억)
  -> 혼동하지 말자. 10억이 나오는 것이 아니다.
  -> log에서 2가 숨겨진 것이다.
  

중요
=> 즉 10억 * 10억은 2로 몇번 나눌수 있냐는 것이고,
빠르게 계산해야 한다.
: 내가 잘하는 2의 거듭제곱 2의 10승이 1024 이고, 10의 3승이다.
그러면 10의 18승이라고 한다면
2의 10승이 6번 진행된거고, 거듭제곱에 사용된 카운트는
=> 10 X 6번이다.

• 2) for문에서 100번을 수행하므로
  -> 100번.
  

• 3번) 로그 계산
  

---

260422 이전.

느낀점

: 왜 이분탐색인가?
어떻게 접근할 것인가????

• 모든 사람이 입국심사 거치는데 걸리는 시간의 최소값을 구하는 문제이다.

맨 처음에 노트로 그림을 그렸을때는
30초가 걸리지 않을까? 생각을 했지만,,,
입출력 설명에서 1분을 더 기다리면 가능하다고 했다.

여기서 코드로 어떻게 구현할것인가에 대해 생각하다가 시간이 지나가버린다!!

일단은 내가 예상한 시간은 30분인데 28분도 가능하다는 것을 통해서
큰 시간을 점점 작게 만드는 탐색을 썻다는 것을 생각해냈어야 했다.
계속 찾아나가는 것이라는 것을 캐치해야 한다.

반대로 생각해야 한다.

n과 times를 이용해 단번에 최소 시간을 구하는 것이 아니라 가능한 시간 내에서 n명을 통과시킬 수 있는 최소 시간을 찾아야 한다.

풀이에 대해 생각해내는 방법

while(min <= max)
    {
        long long sum = 0;
        long long mid = (max + min) / 2;
        
        for(int i = 0; i < times.size(); i++)
        {
            sum += (mid / times[i]);
        }
        
        if(n > sum)
        {
            min = mid + 1;
        }
        else if(n < sum)
        {
        	max = mid - 1;
        }     
        //이렇게 하려고 했으나...
        else 
        {            
            answer = mid;            
        }                
    }

=> 시간이 초과된다. 어쨋든 최소값이면서 answer 값을 줄여나가야 하는 것이므로 코드를 변경했다.

while(min <= max)
    {
        long long sum = 0;
        long long mid = (max + min) / 2;
        
        for(int i = 0; i < times.size(); i++)
        {
            sum += (mid / times[i]);
        }
        
        if(n > sum)
        {
            min = mid + 1;
        }
        else 
        {
        	answer = mid;
        	max = mid - 1;
        }     
                      
    }

음 뭔가 잘못되었군!

=> int는 4바이트이고 long long형은 8바이트이므로 사용된 모든 변수들을 long long으로 변경시키도록 하자!

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

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