[C++]백준 1072 게임 (이진탐색)

1072번: 게임 (acmicpc.net)

1072번: 게임

#include <iostream>

using namespace std;
#define MAX 1000000000

long long X, Y, Z;
int cnt=-1;

int main() {
    cin >> X >> Y;
    Z=(Y*100/X);
    
    if(Z>=99) {
        cout << cnt;
        return 0;
    } 

    int left=0, right= MAX;

    while(left<=right) {
        int mid=(left+right)/2;
        int temp=(Y+mid) * 100 / (X+mid);
        //cout << left << "," << right << ","  << mid << "," << temp << endl;
        if(Z<temp) right=mid-1;
        else left=mid+1;
    }
    
    cout << left;
}

이진탐색(이분탐색) 의 원리라 하면..

어떤 찾고 싶은 값이 있는데 이 값이 분명히 0~ 100000000000 사이에는 있다.

그치만 이것을 0부터 순서대로 찾으면 너무 시간이 오래걸리겠지?

근데 이분탐색을 쓰면 /2 /2 /2.... 이렇게 쪼개가며 영역을 좁혀간다.

시간복잡도가 Olog2이런식으로 된다는건데........... 

아무리 큰 숫자라도 2 몇번 나누면 어떤 영역에 도달하는데에는 정말 금방이 돼 버린다.

시간복잡도가 급격하게 줄어드는 것이다.

 

 예제로 따지면

100 80 을 넣었을 때 80 -> 81이 맨처음으로 되는 그 숫자를 찾는 것인데

이 문제같은 경우엔 left 쪽에는 Z는 80이 유지될 것이고 right쪽으로 갈수록 Z는 99에 가까울 것이다.

그러므로 right를 temp값이 Z보다 작을 때까지 반복하다보면 80의 반복이 끝나는 지점이 right가 될 것이고

그 상태에서 left를 갱신시켜가며 오른쪽으로 옮기면, 처음으로 맞닿는 지점 + 1이 결국 처음으로 z가 81이 되는 지점, 즉 정답이 되는 것이다.

 

---

이런 이분탐색은 첨이라.. 어떤 문제에서 어떤 형태로 이를 쓸 수 있는지 찾고 많이 반복해서 습득할 필요가 있을 것 같다.