99클럽 코테 스터디 1일차 TIL + 이진탐색(C++)

문제

백준 1072번: 게임

https://www.acmicpc.net/problem/1072

 

접근 방법

처음에는 단순히 반복문을 한 번 돌 때마다 x와 y를 증가시켜 승률을 갱신한 후, 기존의 승률과 갱신한 승률을 비교해 두 값이 달라지는 순간 반복문을 돈 횟수를 리턴하는 방식으로 그냥 단순하게 풀었다.

하지만 이렇게 풀었더니 시간초과가 발생했다.

시간초과가 발생하는 이유는 x와 y를 1씩 동시에 증가시키면 y / x 값이 점진적으로만 변하기 때문에, 처음 x와 y가 매우 큰 경우 처음 승률에서 달라지기까지 상당한 시간이 걸릴 수 있기 때문이다.

 

구글링 결과 권장되는 풀이는 이분 탐색 풀이였다.

문제의 요구 사항을 다시 한번 살펴보면, 문제는 특정 승률 이상이 되는 최소의 추가 게임 수 찾기를 요구한다.

이렇게 어떤 함수의 최소/최대 임계점을 찾는 문제의 경우에는 이분 탐색이 권장된다.

이분 탐색을 사용하면 탐색 범위를 절반으로 줄여가며 검색하므로 불필요한 연산을 줄여, 탐색 속도가 O(log n)으로 빨라진다.

 

코드

#include <iostream>
using namespace std;

int main() {
    long long x, y;
    
    cin >> x >> y;
    
    int z = 100 * y / x;
    
    // 소수점을 버리므로 승률은 절대 99%를 넘을 수 없다.
    if (z >= 99) {
        cout << "-1";
        return 0;
    }
    
    int left = 0;
    int right = 1000000000;
        
    while (left <= right) {
        int mid = (left + right) / 2;
        int tmp = 100 * (y + mid) / (x + mid);
        
        if (tmp > z) 
            right = mid - 1;
        else if (tmp <= z)
            left = mid + 1;
    }
    
    cout << left;
    
    return 0;
}

• left는 추가할 게임 수의 최소값으로, right는 최대값으로 초기화하여 이분탐색을 시작하고, 중간값을 계산하여 승률을 비교하며 적절히 범위를 조정한다.
• if (tmp > z): 새로운 승률이 기존 승률 z보다 크면, 추가할 게임 수가 너무 많다는 의미이므로, right를 mid - 1로 조정하여 범위를 줄인다.
• else if (tmp <= z): 새로운 승률이 기존 승률 z보다 작거나 같으면, 추가할 게임 수가 부족하다는 의미이므로, left를 mid + 1로 조정하여 범위를 늘린다.

 

회고

이분 탐색은 항상 머리로는 이해되는데 활용이 잘 안 될 때가 많은 것 같다. 해당 주제 문제를 더 많이 풀어봐야할 것 같다.