[백준/C++] 1072 - 게임

문제 바로가기(백준)

요약

형택이가 더 해야하는 판수를 이분탐색을 통해 찾아야 합니다.

단, 승률(Z) 계산 시 int/double 범위를 초과할 수 있습니다. (1’000’000’000 * 100)

계산 순서에 따라 변수(Z/newZ)를 long type으로 선언하거나, long double로 형변환해야 합니다.

풀이 과정

• 승률(Z)을 계산합니다.

• low = 0(최소판수), high = 1’000’000’000(최대판수)로 승률(Z)이 달라지는 횟수를 탐색합니다.

• 승률(Z)이 변하면(newZ > Z) 결과값(result)을 mid로 갱신합니다.

예외처리

1. result 값을 -1로 초기화
   • 이분탐색에서 단 한번도 갱신이 없다면, Z는 변할 수 없다는 것을 의미합니다.
2. Z가 99 이상이면 -1를 출력
   • 소수점을 반올림 하지 않고 버리기 때문에, 99%는 100%가 될 수 없습니다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int X, Y, Z;
    cin >> X >> Y;
    
    // 승률(Z) 계산
    Z = (long double)Y / X * 100;

    // 승률이 절대 변하지 않으면, binary search에서 값이 변하지 않음 : -1 출력
    int result = -1;
    // binary search - init
    int low = 0;
    int high = 1'000'000'000;

    // binary search 
    while (low <= high)
    {
        int mid = (low + high) / 2;
        // mid판 더 했을때(이겼을때) 승률 계산
        int newZ = (long double)(mid + Y) / (mid + X) * 100;

        // 승률이 변했다면 결과값(result) 갱신, 최소값 탐색
        if (newZ > Z)
        {
            high = mid - 1;
            result = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    cout << result;
}

후기

처음에 Z 계산 시 100을 먼저 곱하면 int 범위가 초과된다고 생각해서 (double)Y / X * 100을 사용했습니다.

하지만 제출해도 계속 틀린 결과로 나와서 long Z = 100 * (double)Y / X 로 변경 후 성공했고, 이후 (double) Y / X * 100이 안되는 이유를 찾느라 헤맸습니다.

계산 시 실수형 범위(double / long double)에 주의해야 할 것 같습니다.