[백준/C++] 1072번: 게임

문제

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

---

문제 요약

형택이는 앞으로의 모든 게임에서 지지 않는다.

 

게임 기록은 현재 다음과 같다.

 

게임 횟수 : X

이긴 게임 : Y

승률 : Z%

 

X, Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 출력한다.

---

코드

#include <iostream>

#define ll long long

using namespace std;

ll x, y, z;

ll res = -1;

void bin_search() {
	ll left = 1;
	ll right = 1000000000;

	while (left <= right) {
		ll mid = (left + right) / 2;

		ll change_z = (y + mid) * 100 / (x + mid);

		if (z < change_z) {
			right = mid - 1;
			res = mid;
		}
		else {
			left = mid + 1;
		}
	}
}

int main() {

	cin >> x >> y;

	z = y * 100 / x;

	bin_search();

	cout << res;

	return 0;
}

---

코드 설명

이진 탐색을 통해 문제를 해결한다.

 

형택이가 게임을 mid 판 진행했을 때,

 

Z가 변화한다면, right = mid - 1 하여 더 적은 판을 수행했을 때도 변화하는지 탐색하고,

+ 이 때, mid값을 먼저 갱신한다. (다음 탐색에서 더 적은 판을 수행해도 변화하면 다시 갱신)

 

Z가 변화하지 않는다면, left = mid + 1 하여 더 많은 판을 수행했을 때는 변화하는지 탐색한다.

---

고찰

문제가 주어졌을 때, 가장 먼저 생각해볼 수 있는 알고리즘은 정답이 될 수 있는 모든 경우의 수를 체크해보는 완전탐색이 있다.

 

하지만 정답이 될 수 있는 수의 범위가 너무 크다면, 정답이 될 수 있는 경우의 수의 범위를 절반씩 줄여가며 체크해보는 이진탐색을 생각해볼 수 있다.

 

 

추가적으로, 이 문제에서 Z(%)를 구할 때, 

 

1. y * 100 / x

 

2. y / x * 100

 

1번식과 2번식은 다른 방식으로 연산된다.

 

1번은 먼저 y와 100을 곱한 정수를 x로 나누어 소수점을 나중에 버리지만,

 

2번은 먼저 y를 x로 나누어 소수점을 버리고, 100을 곱하기 때문에 오차가 발생한다.