백준 1072번 게임

문제 링크입니다: https://www.acmicpc.net/problem/1072

이분 탐색을 이용해 확률을 찾는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 99%의 승률에서 몇번을 이겨도 100%는 될 수 없습니다. 따라서 주어진 X와 Y에 대해 Z가 99 이상이면 -1을 출력합니다.

2. 새로 찾는 확률은 ((Y + 횟수) * 100) / (X + 횟수)입니다.

3. 따라서, low = 0, high = 1,000,000,000으로 두고 이분탐색을 통해 확률이 달라지는 횟수를 찾습니다.

4. tempZ >= Z인 지점에서 결과가 갱신되기 때문에 mid +1 이 결과입니다.

#include <iostream>

using namespace std;

 

const int MAX = 1000000000;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        long long X, Y;

        cin >> X >> Y;

 

        int Z = (Y * 100) / X;

        //확률이 바뀔 수 없는 경우

        if (Z >= 99)

        {

                 cout << -1 << "\n";

                 return 0;

        }

       

        int low = 0, high = MAX;

        int result = -1;

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 //이분탐색 결과 확률

                 int tempZ = (100 * (Y + mid)) / (X + mid);

                 if (Z >= tempZ)

                 {

                         result = mid + 1;

                         low = mid + 1;

                 }

                 else

                         high = mid - 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~