문제

1072번: 게임

풀이

일단 이긴 횟수를 1부터 최대 1000,000,000까지 순회하면서 각각의 경우에 승률을 계산하고, z보다 높은 승률이 나오면 이를 출력하는 방법을 떠올렸다.

하지만, 이 경우에 최대 1000,000,000번 연산을 해야하므로 10초가 걸리면서 시간초과가 뜰 것이다.

→ 다른 방법을 떠올려야 함

배열에 1부터 최대 1000,000,000까지의 숫자를 차례대로 저장하고, 이를 이진탐색 하는 방법을 생각했다.

이진 탐색은 logN 만큼의 시간복잡도를 갖기 때문에 시간초과를 해결할 수 있다. 또한, 이긴 횟수는 1부터 차례대로 탐색하기 때문에, 정렬된 상태로 취급할 수 있다.

→ 따라서 모든 횟수를 이진 탐색 하면서, 현재 탐색중인 횟수만큼 이길 때의 승률을 계산하고, 이 승률이 z보다 크면 값을 갱신한다.

처음에는 배열에 이긴 횟수를 저장하는 방식을 사용했는데, 메모리 초과가 발생하였다.

앞으로 진행 될 게임 횟수는 최대 1000,000,000(= 10억)번이므로, 이를 int형 배열로 생성하면 4000,000,000 바이트(= 4000MB) 공간을 차지하므로 메모리 제한 128MB를 초과하게 된다.

→ 따라서 배열을 사용하지 않고, start, mid, end 값 자체를 이긴 횟수로 사용하는 방법을 생각했다.

#include <iostream>
#include <vector>

using namespace std;

// * z(승률) = (y * 100) / x
// * 앞으로의 모든 게임은 무조건 이긴다.
// ? 지금까지 진 횟수만큼을 이진탐색 -> z + a인 값이 처음 나오는 위치 구하기

int main() {
    int x; long long y; // x: 게임 진행 수, y: 이긴 횟수
    cin >> x >> y;

    int z;
    long long tmp = y * 100;
    z = tmp / x;

    int start = 1, end = x;
    int mid;
    int min_cnt = 1000000000; // 조건을 만족하는 현재까지의 최소 이긴 횟수
    long long min_odds = 100; // 조건을 만족하는 현재까지의 최소 승률 값
    long long current_odds;

		tmp = (y + end) * 100;
    if (tmp / (x + end) == z) { // 아무리 이겨도 승률을 올릴 수 없다면
        cout << -1 << '\\n'; // -1 출력 후 종료
        return 0;
    }

    while (start <= end) {
        mid = (start + end) / 2;
        tmp = (y + mid) * 100;
        current_odds = tmp / (x + mid);
        
        if (current_odds > z) { // z보다 큰 승률이 나왔을 때
            if (current_odds <= min_odds) { // 현재까지의 최소 승률보다 작거나 같을 때
                min_odds = current_odds; // 최소 승률을 갱신
                if (mid < min_cnt) { // 현재 이긴 횟수가 최소 이긴 횟수보다 작을 때
                    min_cnt = mid;
                }
            }
            end = mid - 1; // 더 작은 승률이 나오는지 확인
        } else { // z랑 동일한 승률이 나왔을 때 -> 별도의 작업 필요 없이 재탐색
            start = mid + 1;
        }
    }

    cout << min_cnt << '\\n';

    return 0;
}