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

아이디어 도출해놓고 자료형 실수와 오버플로우를 예측하지 못해 30분동안 삽질한...문제였다...

먼저 향상된 게임실력으로 더이상 지지않는다는 전재가 있으므로 

확률 z = (y(이긴 게임 수)/x(총게임수))*100 이 바뀌기 위해 추가로 진행해야하는 최소의 게임수를 

구하는 문제이다. 최소의 게임수라는 말은 없지만 확률이 변하는 순간의 게임수이므로 최소의 게임

수를 구하면 된다. 

문제 풀이 순서

1. 하한을 0게임으로 잡고 상한을 1000000001로 잡았다(상한 잘못 잡아서 고생했다...)

2. 이분탐색으로 (하한+상한)/2만큼 추가게임을 진행하였을때의 확률을 계산하여 확률이 변하였는지
   확인해본다. 

3. 확률이 변했다면 상한값을 줄이고, 변하지 않았다면 하한값을 중간값+1방식으로 늘려간다. 

4. 이렇게 left <= right를 만족할때까지 진행되므로 결국 하한에 수렴하도록 mid를 설정하고 검사한
     다.

5. 빠저나왔을때의 left값은 확률이 변하는 순간의 하한이다.

자료형과 범위에서 실수로 고생한걸 보면서 한참 멀었구나를 느꼇다...

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

1072번: 게임

1072번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 게임 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 5088 779 578 17.719% 문제 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력

www.acmicpc.net

<Code>

// pda_pro12
#include<algorithm>
#include<iostream>
 
#define INT 0x7fff0000
#define MAX_ 1000000001
 
using namespace std;
 
typedef long long ll;
ll x, y, z; ll lft, rgt;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> x >> y) {
        z = y * 100 / x;
        lft = 0;  rgt = MAX_;
        int ans = z;
        while (lft <= rgt) {
            ll mid = (lft + rgt) >> 1;  // 추가 게임횟수 
            ll per = (y + mid) * 100 / (x + mid);
            if (per > z) {
                rgt = mid - 1;
            }
            else
                lft = mid + 1;
        }
        if (lft >= MAX_) {
            cout << -1 << '\n';
        }
        else
            cout << lft << '\n';
    }
    return 0;
}