[C++][백준] 게임(1072) - 파라메트릭 서치

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X

• 이긴 게임 : Y (Z%)

• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

 

입력

각 줄에 정수 X와 Y가 주어진다.

 

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

 

풀이

파라메트릭 서치를 이용하여 문제를 풀었습니다.

 

현재 승률 Z는 이긴 게임(Y) / 전체 게임(X)입니다.

 

 

 

앞으로 진행하는 모든 게임에서 이긴다고 가정할 때, 몇번 게임을 해야 승률이 Z에서 변하는지 구하는 문제입니다.

 

 

 

이때 최소 게임횟수는 다음과 같이 생각해 볼 수 있습니다.

게임 1판을 했다고 생각하고 승률을 계산합니다.

승률이 변했는지 확인합니다.

 

 

게임 2판을 했다고 생각하고 승률을 계산합니다.

승률이 변했는지 확인합니다.

 

 

게임 3판을 했다고 생각하고 승률을 계산합니다.

승률이 변했는지 확인합니다.

 

그러나 해당 방법은 너무나 느리고 비효율적입니다. 

이런 케이스에서 파라메트릭 서치는 탐색을 O(N)에서 O(logN)으로 줄여줄 수 있습니다.

 

파라메트릭 서치의 start를 1, end를 충분히 큰 수로 설정하고 로직을 수행하면 승률이 변하는 게임의 최소횟수를 구할 수 있습니다.그 어떤 케이스에도 승률이 변하지 않는 경우에는 end값이 변하지 않았을 것입니다.이 케이스만 고려하면 되는 문제였습니다.

 

전체 소스 코드는 아래와 같습니다.

#include <iostream>

using namespace std;

long long X, Y, Z;
long long MAX = 2000000000;

bool possible(long long num) {
	long long Z2 = (Y + num) * 100 / (X + num);
	if (Z2 != Z) return true;
	else return false;
}

long long solution() {
	long long start = 1, end = MAX;

	while (start < end) {
		long long mid = (start + end) / 2;

		if (possible(mid)) {
			end = mid;
		}
		else {
			start = mid + 1;
		}
	}

	if (end == MAX) return - 1;
	else return end;
}

int main() {
	cin >> X >> Y;
	Z = Y * 100 / X;
	cout << solution();
	
	return 0;
}