[백준 1072] 게임 (C++)

문제 링크: https://www.acmicpc.net/problem/1072

1072번: 게임

1. 주의할 점

- 2가지 방식으로 풀었는데, 이 중에서 이분탐색을 사용할 경우 High에 충분히 큰값을 할당해야한다.

- 소수점은 버린다고 했으므로 Double을 사용하지 않고 Long Long을 사용해 소수점 이하는 자동으로 버리도록 한다.

 

2. 구현

- 첫 번째 방법: 이분탐색

  Low: 0, High: 2,000,000,000 으로 할당해준다. High의 경우 충분히 큰 값을 할당해야 하는데 얼만큼 큰 값을 할당해야    할지 확실하지 않아서 최대값의 2배를 할당했다.

  이후 Mid값에 승률이 달라진다면 High를 낮추고 그 반대의 경우는 Low를 높이는 방식으로 접근한다.

 

- 두 번째 방법: 수학적 계산

  승률 Z : 100*Y/X  -> Z <= 100*Y/X < Z+1

  추가 게임 : N번   -> N번 추가 승리 후 승률 : 100*(Y+N)/(X+N)

  추가 게임으로 인해 승률이 올라가려면 100*(Y+N)/(X+N) >= Z+1을 만족하면 된다

  위의 식을 정리하면 N <= ((Z+1)*X - 100*Y)/(99-D)를 만족한다.

  만약 N이 소수점을 포함했다면 해당 수에 대해 올림값을 지녀야한다. 소숫점이하가 0이라면 해당 값을 그대로 지닌다

  위의 정리를 만족하는 N을 구하면된다.

  단, 이 경우는 승률인 Z가 이미 99라면 더 이상 승률이 오를 수 없으므로 예외처리를 해야한다.

 

 

[이분탐색]

#define MAX 9876543210
#include <iostream>
using namespace std;

long long x, y, low = 0, mid, high = 2000000000, z, ans = MAX;
bool cal(long long val) {
	long long temp = (y + val) * 100;
	temp /= (x + val);
	if (temp != z) return true;
	return false;
}

int main() {
	cin >> x >> y;
	z = (100 * y) / x;
	while (low <= high) {
		mid = low + (high - low) / 2;
		bool res = cal(mid);
		if (res) {
			high = mid - 1;
			ans = mid;
		}
		else low = mid + 1;
	}
	if (ans == MAX) cout << -1;
	else cout << ans;
	return 0;
}

 

 

[수학적 계산]

#include <iostream>
using namespace std;
long long x, y, z, ans, mod;
int main() {
	cin >> x >> y;
	z = (100 * y) / x;
	if (z >= 99) cout << -1;
	else {
		ans = (z + 1)*x - 100 * y;
		mod = 99 - z;
		if (ans%mod == 0) cout << ans / mod;
		else cout << ans / mod + 1;
	}
	system("pause");
	return 0;
}