오늘의 학습 키워드

• 특정 k 값을 찾는 것 = 이분탐색으로 구현
• 일관되게 문제를 접근하자

[백준] 게임 - 1072 (C++)

• [백준] 게임 - 1072
• Silver III
• C++ 풀이

문제해설

게임 횟수 : X
이긴 게임 : Y (현재 승률 Z%)
이후 게임이 무조건 이긴다는 가정 하에 현재의 승률Z(%) = (X / Y) * 100가 Z + 1러 바뀌는 최소의 게임 횟수(k)를 찾는 문제이다.

접근법(2)

첫번째 접근법: 수식 전개

좌항에 k만 놔두도록 식을 전개했다. 수학 문제를 푼 셈..

1. 새로운 승률 Z + 1이 되기 위한 조건

2. 부등식 전개 (좌항은 k만)

#include <bits/stdc++.h>
using namespace std;

long long X, Y;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    long long k = ((Z + 1) * X - 100 * Y + (100 - (Z + 1)) - 1) / (100 - (Z + 1));
    cout << k;
    return 0;
}

두번째 접근법: 이분 탐색

단순히 만족하는 값을 찾는 것이 목표인 경우, 이분 탐색이나 브루트포스를 사용해 원하는 조건을 충족하는 최소의 k를 찾는 방법이 더 적합하다.
k의 범위가 0 ~ 1,000,000,000 사이로 브루트포스하면 시간초과가 발생한다. 따라서, O(log N)의 시간 복잡도를 가진 이분 탐색으로 구현하는 것이 타당하다.

C++로 작성 시, 정수 연산 순서에 유의하자

int Z = (Y * 100 / X); // 연산 순서 유의

아래의 수식은 다른 결과가 나온다. 좌변은 $(\times 100)$을 먼저 해서 문제가 없지만, 우변은 $(Y \div X)$ 할 때, 정수 연산으로 나머지가 없어지므로 의도치 않은 잘못된 출력을 야기한다.

$(Y \times 100 \div X) \neq (Y \div X \times 100)$

#include <bits/stdc++.h>
using namespace std;

long long X, Y, k;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> X >> Y;
    int Z = (Y * 100 / X);
    if (Z + 1 >= 100) {
        cout << -1;
        return 0;
    }
    int start = 0, end = 1000000000, mid;
    while(true){
        mid = (start + end) / 2;
        int next_Z = int((Y + mid) * 100 / (X + mid));
        if (next_Z < Z + 1){
            start = mid + 1;
        }
        else {
            k = mid;
            end = mid - 1;
        }
    }
    cout << k;
    return 0;
}

오늘의 회고

특정 k값을 찾는 것은 이분탐색으로 푸는 것이 가장 일반적이다. 브루트포스도 가능하지만, 시간 초과를 발생하는 경우가 허다하기 때문에 빠르게 유형 파악하는 것이 중요한 문제였다.
처음에는 특정 k값을 찾기 위해 수식을 전개했다. 하지만, 이런 방식은 실제 코딩 테스트 때 실수가 발생할 수 있기 때문에 피하는 것이 좋다. 수학 문제를 푸는 것이 아니라는 것을 명심하자!