[C++, python] 백준 1072번 풀이 ( 게임 )

- 문제 ( 1072번 ) : 게임

• 링크 : https://www.acmicpc.net/problem/1072

• 형택이가 최소 몇번의 게임을 더 해야 승률이 변하는지 구하는 프로그램

  • 처음에 플레이한 게임횟수와 현재까지 이긴 게임의 수를 입력으로 받음.
  • 이 후부터 플레이한 게임은 반드시 이긴다.
  • 게임기록은 삭제할 수 없음.

---

- 입력 및 출력

[ 입력 ]

• 각 줄에 게임을 플레이한 총 횟수 ( X ), 현재까지 이긴 게임 횟수 ( Y ) 입력.

  [ 입력범위제한 ]

  • 1 ≤ X ≤ 1,000,000,000
  • 0 ≤ Y ≤ X

[ 출력 ]

• 형택이가 승률을 올리기 위해 플레이해야하는 최소한의 게임 수 출력.
• 만약 승률 ( Z ) 가 절대 변하지 않는 경우라면 -1 출력

---

- 문제 풀이

• 이번 문제는 2가지 방법으로 풀 수 있다.

  1) 승률이 변하는 판수를 수식으로 풀어서 구현
  2) 플레이하는 판수를 변경해가며 매번 직접 승률을 구해보는 방법

  이렇게 두가지 방법 중 나는 2번째 방법으로 해결했다.
  

• 2번째 방법으로 구현할 때 1부터 최대값인 1,000,000,000 까지 일일히 대입하다보면 당연히 시간초과가 난다.
  그래서 하나씩 대입하는 것이 아닌 이진탐색을 사용해서 값을 구하려고 한다.

  • 이진탐색에 대한 내용은 아래 링크에 정리해놨다!
    https://velog.io/@jmink002/Binary-Search

• 이 문제에 이진탐색을 적용해 문제를 해결하는 과정은 다음과 같다.

  1. 입력받은 x 와 y 값을 가지고 z 를 먼저 구한다.
  2. 1에서 구한 z 가 99 % 이상이면 -1을 출력 후 프로그램을 종료한다.
     ( ∵ 승률의 소숫점은 반올림이 아닌 버림이며, 앞으로 플레이하는 게임은 무조건 승리한다.)
  3. 2의 조건을 만족하지 못하는 경우, 이진탐색으로 최적의 값을 찾는다.
     ( 여기서 최적의 값이란 승률을 올리기 위해 플레이해야하는 최소한의 게임 수)
  4. left = 0, right = 1,000,000,000 으로 놓은 후, 이것의 중앙값 ( mid ) 를 앞으로 플레이할 게임의 수로 놓고 newz 를 계산한다.

     • 즉, newz = 100 * (y + mid) / (x + mid) 이다.

  5. 그 후 newz 와 z 를 비교해 탐색범위를 줄여가며 최적의 값을 찾는다.

     • 탐색범위는 다음의 2가지 경우로 나눠 조정한다.

     1. z < newz 인 경우 : mid 를 기준으로 왼쪽 범위로 조정
        => 최소 판수를 구해야하니 플레이할 판수를 줄인다.
        => right = mid - 1 로 변경 후 다시 계산
     2. z == newz 인 경우 : mid 를 기준으로 오른쪽 범위로 조정
        => 현재의 mid 만큼의 게임을 더 하더라도 승률이 바뀌지 않은 것이므로 판수를 더 늘린다.
        => mid 를 증가시켜야하므로 left = mid + 1 로 변경 후 계산

• 이진탐색이 끝났다면 그때의 left 값을 출력하면 문제 해결!

---

- 최종 코드

• c++ code

#include <iostream>
using namespace std;

int calc_rate(long long x, long long y) {
  return (100 * y) / x;
}

int main() {

  // Declare three variables
  // 0 < x <= 1,000,000,000 
  //   => the range of "y" exceed the range of "int"
  // So, these variables are declared as the range of "long long"
  long long x, y, z;
  int count = -1;

  // input x and y
  // x is total plays
  // y is win games
  cin >> x >> y;

  // calculate z 
  z = calc_rate(x, y);

  // if z >= 99%, then print "-1"
  if (z >= 99) {
    cout << count << endl;
    return 0;
  }

  // if z <= 99, find result with binary search
  int left = 0;
  int right = 1000000000;
  int mid = 0;

  while (left <= right) {
    mid = (left + right) / 2;
    long long newz = calc_rate(x+mid, y+mid);

    // if z < newz, then reduce the number of rounds
    if (z < newz) {
      right = mid - 1;
    }

    // else, increase the number of rounds
    else {
      left = mid + 1;
    }
  }

  // print result
  cout << left << endl;

  return 0;
}

• python code

# calculate z
def calc_rate(x, y):
  return (100 * y) // x


# input x, y
x, y = map(int, input().split())
z = calc_rate(x, y)

# if z >= 99 then print "-1"
if z >= 99:
  print(-1)

# else find value with binary search
else:
  left = 0
  right = 1000000000
  
  while (left <= right):
    mid = (left + right) // 2
    newz = calc_rate(x+mid, y+mid)
  
    # if z < newz then reduce the number of rounds
    if (z < newz):
      right = mid - 1
  
    # else increase the number of rounds
    else:
      left = mid + 1
  
  print(left)