[알고스팟] 문제 아이디 : RATIO 승률 올리기

문제

싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다. 처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 승리를 하게 되었다.

스파이더 게임을 하면 플레이어에 대한 정보가 다음과 같이 주어지는데 싸비는 이것을 보다 표시되고 있는 승률을 1%이상 올리기 위해선 최소한 몇 번의 연승이 필요한지 의구심이 들었다.

플레이 횟수 : N
승리 횟수 : M(Z %)

여기서 Z%의 경우 소수점을 제외한 부분의 승률이다. 즉, 승률이 88.68% 일 경우 Z = 88% 이다.

N, M이 주어졌을 때, Z를 올리기 위한 최소한의 연승횟수가 필요한지 구하는 프로그램을 작성하라. 여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다.

입력

입력의 첫번째 줄에는 테스트 케이스의 개수 T가 입력되고, 다음 줄 부터 한줄에 하나씩 T개의 테스트 케이스가 입력된다.
테스트케이스는 두 개의 숫자로 이루어진다. 처음에 들어오는 숫자는 스파이더를 플레이를 한 횟수N(1<=N<=1,000,000,000)를 의미하며, 나중에 들어온 숫자는 승리한 횟수M(0<=M<=N)를 의미한다.

출력

각 테스트 케이스에 대해서 한줄에 승률을 올릴 수 있을 경우 이를 위한 최소한의 연승 수를 출력하며, 불가능할 경우 -1을 출력한다.

 

이 문제는 백준의 게임 문제와 완벽하게 일치한다. 

 

다만 다른 점은 백준 게임 문제는 테스트 케이스 입력하는 부분이 없다.ㅎㅎ

 

아무튼...

 

이 문제를 풀기 위해서는 머릿속으로 최솟값이 어떤것인지.. 최고 값이 뭔지 생각해야 한다.

 

0인지 아니면 배열의 맨 처음것인지 곰곰히 생각해야한다.

이게 핵심이다.

 

이건 몇판 더 하는지 모르는 상황이다. 어찌 되었든... 그 값을 구해줘야 한다.ㅎㅎ

 

#include <bits/stdc++.h>
using namespace std;

int L = 2000000000;

int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int k;
  cin >> k;
  while(k--) {
  long long n,m;

  cin >> n >> m;

  long long current = (m*100)/n;

  long long left = 0;
  long long right = L;
  
  int result = -1;
  while(left <= right) {
    long long mid = (left + right) / 2;
    long long increse = ((m+mid) * 100)/(n+mid);

    if (current < increse) {
      result = mid;
      right = mid -1;
    } else {
      left = mid +1;
    }

  }
  cout << result << "\n";
}
}

핵심은 mid값이 더 게임을 진행하는 정도로 이해하면 될 것 같다.

 

왜 result가 -1인 이유는

절대로 불가능 한경우 즉, 99%일때 경우를 생각해보자.

즉 100판중에 99판 경우인데 이 경우에는

아무리 해도 101 -> 100판 102 -> 101판 이런식으로 증가 될 수 밖에 없다. 

그렇기 때문에 99%에서 1퍼가 증가하려면 다 이겨야 한다는 건데

이건 말이 되지 않는다. 그렇기 때문에 -1을 해두었다.