[BOJ 1072] 게임(C++)

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

1072번: 게임

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z %)
• Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램을 작성하시오.

 

 

 

몇 판을 더하는 횟수를 a라고 하면,

 

 

 

(X  + a) / (Y + a) >= (X / Y) + (1 / 100) 을 구하기 위해선, 양변에 Y를 곱해야 하는데, Y의 최댓값이 1,000,000,000이므로, 표현할 수 있는 범위를 넘어서게 된다.

 

 

 

따라서, 위의 방법으로 문제를 해결하지 않고, 더하는 횟수 a를 직접 탐색(브루트 포스)하면서 값을 찾아야 한다.

 

 

 

a의 범위를, 1에서 1,000,000,000(Y의 최댓값이 1,000,000,000)이라고 하면 된다.

 

 

 

순차적으로 탐색하면, 시간복잡도가 크므로 이분탐색을 통해서 문제를 해결하면 된다.

 

 

 

아래의 해설코드와 비슷하게 작성했는데 틀리는 경우가 있을텐데, 이 부분을 유의해서 보자.

 

 

 

Z = Y * 100 / X

Z = Y / X * 100

 

 

 

위의 두개의 식의 차이가 있다. 첫 번째식은, 정수의 나눗셈만으로 정답을 구할 수 있다. 

 

 

 

하지만 두 번째 식은, 부동소수점 연산이 필요하다.

 

 

 

컴퓨터의 부동소수점 연산은 100% 정확하지 않다는 것을 유념하면, 첫 번째 식으로 문제를 풀어야 된다.

 

 

 

해설코드(C++).

 

#include <iostream>
using namespace std;
 
long long n_max = 1000000000;
long long n_min = 0;
long long X, Y;
long long Z;
long long answer = -1;
 
int main() {
    cin >> X >> Y;
    Z = Y * 100 / X;
    
    while(n_min <= n_max){
        long long mid = (n_max + n_min) / 2;
        long long new_Z = ((Y + mid) * 100 / (X + mid));
        
        if(new_Z > Z){
            n_max = mid - 1;
            answer = mid;
        }else{
            n_min = mid + 1;
        }
    }
    
    cout << answer << endl;
    return 0;
}