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

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

 

난이도 : 실버 3 
알고리즘 유형 : 이분탐색 
풀이 시간 : 35분 

문제 풀이 

X ≤ 1000000000 으로 주어졌기 때문에 완전탐색으로 풀면 시간초과가 날 것이라고 판단하였다.

따라서, 이분탐색 알고리즘을 사용해 Z가 증가하는 최솟값을 찾아주는 방법을 사용하였다.

여기서, 조절해주어야 하는 값은 "이후 실시한 게임 수"로 정하였다.

왼쪽(left) : 0

오른쪽(right) : X의 최댓값(1000000000)

중앙값(mid) : 실시한 게임 수

 

※ 주의할 점 ※

1. 최댓값의 범위가 매우 크기 때문에, int형 대신 long long int형을 사용하였다.

2. 확률 Z 계산 시, c++의 부동소수점 계산 오차를 방지하기 위해 100을 먼저 곱해주었다.

3. 이분탐색을 진행하기 전, 확률 Z를 더이상 올릴 수 없는 경우에 대한 예외 처리를 진행해주었다.

 

코드

/*
1072. 게임

형택이는 모든 게임에서 지지 않는다.
이전 기록떄문에 현재 실력 증명이 안된다고 생각함.

- 게임 횟수 : X
- 이긴 게임 : Y(z%)
z는 형택이 승률이다. Y * 100 / X

X, Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하기

풀이:
X <= 1000000000이기 때문에, 완탐 시도하면 시간초과난다.
: 이분탐색으로 문제 해결하기
- 게임은 항상 이기기 떄문에 X와 Y가 점진적으로 증가한다.
- z가 변하기만 하면 된다.

left : 0
right : 1000000000
*/

#include <iostream>
#include <algorithm>
#define lli long long int

using namespace std;

lli x, y, z;
lli ans = 1000000000;

int main() {
	cin >> x >> y;
	z = y * 100 / x;

	// 시작하지 못하는 경우
	if (z >= 99) {
		cout << -1 << '\n';
		return 0;
	}
	
	// 이분탐색 
	lli left = 0;
	lli right = 1000000000;
	lli new_z, mid;

	while (left <= right) {
		mid = (left + right) / 2;
		// 새로운 z 구하기
		new_z = (y + mid) * 100 / (x + mid);
		// 게임 수 늘리기
		if (z >= new_z)
			left = mid + 1;
		else {
			right = mid - 1;
			ans = mid;
		}
	}

	cout << ans << '\n';

	return 0;
}

배운 점 

초반에는 계산식을 float(y) / x * 100으로 잡고 진행하였는데, 계산에 오차가 발생하였다. 이후, 문제를 다시 읽어 정수형으로 먼저 계산해준 뒤, 소숫점은 자동으로 버려지는 방식으로 진행하자 문제가 해결되었다. 이러한 이유는 c++의 연산 처리 방식에 따라 차이가 발생한다는 점을 알았다.

이분탐색은 범위 설정에 신경을 많이 써야하고, 계산 시 정밀도를 잘 생각하며 풀어야겠다.