BaekJoon 1072 게임

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

소스결과 1984 KB / 0ms

출처 Baekjoon

언어 C++17

분류 수학 이분탐색 브루트포스 탐색

 

설명

Spider Solitaire를 즐기는 형택이가 현재 게임 승률에서 몇 판 더 했을 때 자신의 승률이 바뀌는지 알아보자.

 

처음에는 예외를 잡는 부분이 생각보다 어려웠다. 최대 시도를 10억번을 기준으로 이분 탐색을 진행해서 10억이 넘어가면 -1로 출력하는줄 알았으나.

질문 게시판을 보고 그냥 승률이 99%가 넘는다면 예외 조건은 존재하지 않는다.

0 ~ 10억 + a로 해서 이분탐색을 진행 하는게 그저인 문제. 기준은 초기 z값을 기준으로 현재 게임 수를 더한 임시 tempZ가 작거나 같으면 최소 범위를, 반대인 경우 최대 범위를 축소 시키면 된다.

 

문제에는 명시가 안되어 있지만. TCC가 1개로 한정 된게 아니라. 여러 개 존재한다. EOF를 통해 계속 입력 받도록 해야한다.

 

알고리즘

1. x, y 를 받아 z를 계산한다.

2. z가 99 이상인 경우 -1을 출력, 이외의 경우 3을 진행한다.

3. 최소 범위 0, 최대 범위 10 + a를 기준으로 최대 최소 범위가 같거나 바뀔 떄 까지 이분 탐색을 진행한다.

 3 - 1. 중간값 m을 각각 x 와 y에 더했을 때의 승률을 계산해 기존 승률 이하인 경우 최소 범위를, 초과 인 경우 최대 범위를 조정한다.

 3 - 2. 최소 범위를 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1500000000;

int main()
{
	int res = -1;
	long long x, y;
	int z;

	while (cin >> x >> y)
	{
		long long left = 0, right = MAX;
		z = 100 * y / x;

		if (z >= 99)
			left = -1;
		else
		{
			while (left <= right)
			{
				long long middle = (left + right) / 2;
				long long cal = 100 * (y + middle) / (x + middle);

				if (cal <= z)
					left = middle + 1;
				else
					right = middle - 1;
			}

		}
		cout << left << '\n';
	}

	return 0;
}