Boj 1072) 게임

문제

백준 1072

설명

어찌 풀어야할지 고생을 했는데, 아래의 주석대로 풀면 수식으로 풀린다. 처음 떠올린 수식은 수식의 아랫부분 식이었는데, f 가 부동소수가 되어서 오차가 심하게 발생하여 쓸 수가 없었다. 위 수식은 모두 100을 곱해서 정수단위로 만들고 현재 소숫점을 정수로 저장해서 사용하므로 결과적으로 정수끼리의 계산으로 처리되어 한번의 나눗셈으로 값을 구할 수 있게 된다. 한번의 나눗셈은 ceil 함수로 커버할 수 있으므로 오차는 문제가 되지 않는다.

double(x)*100 / y 여기도 double(x)/ y * 100 하면 0.799999 이러한 오차문제에 빠지게 된다. 우리가 관심있는 것은 소숫점 2번째 값까지 이므로 미리 100 을 곱하면 정수단위로 넘어가 부동소수점 문제에서 벗어난다.

시간 복잡도

O(1)

코드

/*
(int)100*X/Y + 1 = n + 1 <= 100(X+t)/(Y+t)
(n+1)Y + (n+1)t = 100(X+t)
(n+1)Y - 100X = (99 - n)t

f 만큼의 소숫점이 모자람
X/Y + f = (X+t)/(Y+t)
X + fY + (X/Y + f)t = X+t
fY = (1 - f - X/Y)t
fY*Y/(Y - fY - X) = t; // 소숫점을 곱하고 나누므로 오차가 심함.
*/
using ll = long long;
int main()
{
	ll x, y;
	cin >> y >> x;

	ll ans = -1;
	if (y > x && double(x) / y < 0.99) {
		int n = double(x)*100 / y;  // 0.099999 error 방지용
		ans = ceil(((n + 1) * y - 100 * x) / (double)(99 - n));
	}
	
	cout << ans;
}