[백준] 1072번 게임 (C++) - binary search

문제

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

1072번: 게임

코드

#include <iostream>

using namespace std;

int main(){
  long long x,y;
  cin >> x >> y;
  long long z=100*y/x;
  long long start=0;
  long long end=x;
  long long result=-1;
  while(start<=end){
    long long mid=(start+end)/2;
    long long k=100*(y+mid)/(x+mid);
    if(k>z){
      result=mid;
      end=mid-1; 
    }else{
      start=mid+1;
    }
  }
  cout << result << ' ';
  return 0;
}

정리

(1) z=(double)y/x*100이라고 하면 문제가 풀리지 않고 (2) z=100*y/x라고 하면 문제가 잘 풀린다.

(1) 같은 경우는 소수점까지 구하고 100을 곱하는 방식이고 (2)는 100을 y에 먼저 곱하고 x로 나누어서 그 몫을 구하는 방식이다.

정확하지는 않지만 (1)의 경우에는 소수점 연산을 하기 때문에 문제가 되는 것 같다. 컴퓨터에서 소수점을 구할 때 약간의 오차가 있다고 어디선가 들어본 적이 있다.

퍼센트나 분수와 같은 문제가 나올 경우 되도록 소수점 연산을 하는 방법은 피해야겠다.

 

참조

https://mapocodingpark.blogspot.com/2020/02/BOJ-1072.html