[백준 1072] 게임

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

1072번: 게임

 

투포인터 문제이다.

코드는 어렵지 않지만 투포인터를 떠올리긴 쉽진 않은거 같다 ㅠ

while문을 돌리면 TLE가 발행한다.

 

이 문제의 또다른 포인트는 롱롱과 인트 범위라고 생각하는데

승률을 구하는 경우 소수점 아래는 버림하므로 먼저 100을 곱하고 시작하는 게 맞다.

이 경우 분자의 최댓값이 10^9이므로 100을 곱하면 INT 범위를 넘어선다. 따라서 N과 D는 롱롱이 되어야 한다.

int getWinRate(long long d, long long n)
{
  return n * 100 / d;
}

 

++ 그리고 또 하나, 승률이 99퍼인 경우 아무리 여러 번 게임을 해도 승률이 100퍼가 될 수 없다.

 

정답 코드는 아래와 같다.

#include <stdio.h>

using namespace std;
long long x, y;
int result;

int getWinRate(long long d, long long n)
{
  return n * 100 / d;
}

int main(void)
{

  scanf("%lld%lld", &x, &y);
  int z = getWinRate(x, y);

  if (z >= 99)
    return !printf("-1\n");

  int start = 1, end = 1000000000;
  while (start <= end)
  {
    int mid = (start + end) / 2;
    int newZ = getWinRate(x + mid, y + mid);
    if (newZ == z)
    {
      start = mid + 1;
    }
    else
    {
      end = mid - 1;
      result = mid;
    }
  }

  printf("%d", result);
  return 0;
}