백준 1072_게임(C++)

 

www.acmicpc.net/problem/1072

1072번: 게임

[문제 풀이]

이분 탐색을 이용하여 문제를 풀었습니다.

 

이 문제는 승률 Z를 변화시킬 수 있는 최소 게임판 수를 구하는 문제였습니다. 

X의 최대값이 10억이기 때문에 브루트 포스로 문제를 해결하려 할 경우 시간초과가 납니다. 따라서 이분 탐색을 이용하여 문제를 해결했습니다.

 

이용한 로직

• left = 0, right = X 로 초기화합니다.
• 이분 탐색 중에 나온 mid의 값이 승률을 변화시켰다면 값을 비교해줍니다.
• 이분 탐색 중에 나온 mid의 값이 승률을 변화시키지 못했다면 더 큰 값을 찾아줍니다.

[코드]

#include<iostream>

using namespace std;

long long int X, Y, answer = 1000000000;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> X >> Y;

	long long int Z = 100 * Y / X;

	if (Z == 100 || Z == 99) {
		cout << -1 << endl;
		return 0;
	}

	long long int left = 0;
	long long int right = X;

	while (left <= right) {

		long long int mid = (left + right) / 2;

		if (Z < 100 * (Y + mid) / (X + mid)) {
			if (answer > mid)
				answer = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	cout << answer << endl;

	return 0;

}