[C++] 백준 1072번 - 게임

 

어제에 이어 이분탐색 문제~~~

 

문제1072번

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

1072번: 게임

 

여기서는 X가 1~1000,000,000이기 때문에 이대로 그냥 코드를 짜면 시간 초과가 나온다. 그래서 필요한 것이 이분 탐색이다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정이다.

 

'만약 Z가 절대 변하지 않는다면 -1을 출력한다.' 이게 무슨 소리인지 모르겠어서 찾아봤는데

Z가 100이면 101%로 올라갈 수 없고, Z가 99면 이미 전적에 패배가 있기 때문에 몇 경기를 더 이기는 100%로 올라갈 수 없다고 한다.

 

그리고 start, mid, end 세 변수를 만들어 start와 end에는 0과 1,000,000,000을 넣어주고, mid에는 이 사이의 값을 넣어준다. while문을 사용하여 반복을 해주고 게임을 몇 판 더 해야하는지 알기 위해 z에 mid를 더한 식을 넣어 Z와 비교해준다. 만약 Z가 z보다 크거나 같다면 mid이후의 범위에 원하는 값이 있는 것이기 때문에 mid+1을 시작값에 넣어주고, 반대의 경우라면 end에 mid-1을 넣어준다. 그렇게 반복문을 다 돌면 최소 몇 판을 더 해야하는지 알고 싶은 것이니까 start를 출력해준다.

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

int main() {
	long X, Y, Z;
	cin >> X >> Y;
	Z = (Y * 100 / X);

	if (Z >= 99) {	//99%는 아무리 해도 100%가 되지 않음
		cout << -1;
		return 0;
	}

	int start = 0, end = MAX;

	while (start <= end) {
		int mid = (start + end) / 2;
		int z = (Y + mid) * 100 / (X + mid);

		if (Z >= z) {
			start = mid + 1;
		} else {
			end = mid - 1;
		}
	}

	cout << start;
}