[백준 문제 C++] 1072 게임

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

1072번: 게임

#include <stdio.h>

long long BinarySearch(long long start, long long end, long long x, long long y, long long z)
{
	long long mid, z2;
	long long result = -1LL;

	while (start < end)
	{
		mid = (start + end) / 2LL;
		z2 = (y + mid) * 100LL / (x + mid);

		if (z2 <= z)
		{
			start = mid + 1LL;
		}
		else if (z < z2)
		{
			end = mid;
			result = end;
		}
	}

	return result;
}

int main()
{
	long long x, y, z, result;

	scanf("%lld %lld", &x, &y);
	z = y * 100LL / x;

	result = BinarySearch(0, x + 1, x, y, z);
	printf("%lld\n", result);
}

이진 탐색을 활용하여 결과를 구할 수 있었다.

 

퍼센트로 나타내기 위해선 소수점 2자리만 필요하기 때문에 100판 중 40판을 이겼다면

40 * 100 / 100 으로 정수형이기 때문에 소수점을 제외하고 나타낼 수 있다. ( 4000 / 100 = 40 )

이 때 int형은 오버플로우가 발생할 수 있기에 모두 long long 형으로 설정해주었다.

 

계산 중 실수했던 부분이 게임을 이길수록 전체 판수도 함께 증가해야 된다는 것이었다.

새로운 승률 z2 = (기존 승리 + 추가 승리) * 100 / (전체 판수 + 추가 승리)

 

BinarySearch 매개변수인 long long end 값은 전체 판수 + 1 (x + 1)로 해주었다.

이 값이 현재 로직에서 탐색의 최대 범위이다.

 

전체 판수 : 1000000000 (10억)
이긴 판수 :  980000000 (9억 8천)

 

위의 경우는 총 10억판을 이기면 승률이 98%에서 99%로 올라가게 된다. (1980000000 / 2000000000)

근데 이진 탐색 로직을 보면 z < z2 (기존 승률 < 새로운 승률) 인 경우에만 result를 갱신하게 된다.

end 값이 줄어들어야 result가 갱신이 되는데 end값이 곧 정답이기에 작아질 수가 없기 때문이다.