백준 1072번 문제

오늘의 학습 키워드

이분탐색

문제

백준 1072번 문제

게임 횟수 X와 이긴 게임 횟수 Y가 주어졌을 때 이후의 모든 게임을 이긴다고하면
게임을 최소 몇 번 더 해야 소수점을 버린 승률이 변하는지 구하세요.
만약 승률이 절대 변하지 않는다면 -1을 출력하세요.

풀이 1

설명

이 풀이에서는 승률이 99% 이상일 경우에는 승률이 변할 수 없기 때문에 -1을 출력합니다.
이후에 while문을 돌며 게임 횟수 X와 이긴 횟수 Y를 1씩 증가시키며 기존 승률과 새로운 승률을 비교합니다.
이때 두 승률이 다르다면 있다면 while문을 반복한 횟수를 출력합니다.

정답

#include <iostream>

using namespace std;

int main()
{
	long long X, Y;
	cin >> X >> Y;
	
	long long OldWinRate = (long long)((double)Y * 100.0 / (double)X); // 기존의 승률
	// 승률이 절대 변하지 않는 경우 = 승률이 99% 이상일 때
	if (OldWinRate >= 99)
	{
		cout << -1 << "\n";
		return 0;
	}

	long long i = 0; // while문을 반복한 횟수
	while (true)
	{
		i++;
		X++;
		Y++;
		long long NewWinRate = (long long)(((double)Y * 100.0 / (double)X)); // 새로운 승률
		if (NewWinRate != OldWinRate) // 승률이 변했을 경우
		{
			cout << i << "\n";
			return 0;
		}
	}
}

겪었던 문제

승률을 Y * 100 / X의 방법으로 구하고 제출할 경우 시간 초과로 틀립니다.
그 이유는 정수형 나눗셈은 부동소수점 나눗셈보다 느리기 때문입니다. 연산 속도에 대한 문서
그렇기에 승률을 부동소수점을 사용한 (double)Y * 100.0 / (double)X의 방법으로 구해야 합니다.

또한 승률을 (double)Y / (double)X * 100.0의 방법으로 구하고 제출할 경우
부동소수점 문제 때문에 정답 제출 시 4%에서 문제가 틀릴 수 있습니다.
이를 해결하기 위해서는 승률을 (double)Y * 100.0 / (double)X의 방법으로 구해야 합니다.

풀이 2

설명

풀이 1도 정답이지만 이분탐색을 사용하여 코드를 더 빠르게할 수 있다고 생각하여 새롭게 풀었습니다.
이 풀이에서는 풀이 1과 마찬가지로 승률이 99% 이상일 경우에는 승률이 변할 수 없기 때문에 -1을 출력합니다.
이후에 left와 right의 가운데 값을 사용하여 새로운 승률을 구하고
기존 승률과 변경점이 있다면 최대값이 더 작다고 생각하여 right값을 감소시키고
기존 승률과 변경점이 없다면 최소값이 더 크다고 생각하여 left값을 증가시킵니다.
그러다 left값이 right값보다 커진다면 탐색을 종료하고 left값을 반환합니다.

정답

#include <iostream>

using namespace std;

int main()
{
	long long X, Y;
	cin >> X >> Y;

	long long OldWinRate = Y * 100 / X; // 기존의 승률
	// 승률이 절대 변하지 않는 경우 = 승률이 99% 이상일 때
	if (OldWinRate >= 99)
	{
		cout << -1 << "\n";
		return 0;
	}

	// 이분탐색
	int left = 0; 
	int right = 1000000000; // X의 최대 값이 1000000000이기 때문에 이분탐색의 범위도 1000000000까지
	while (left <= right) // 최솟값을 구할 때까지 반복
	{
		int mid = (left + right) / 2; 
		int NewWinRate = (Y + mid) * 100 / (X + mid); // 새로운 승률

		if (NewWinRate != OldWinRate) // 승률이 변했을 경우
			right = mid - 1; // right 감소
		else
			left = mid + 1;  // left 증가
	}

	cout << left << "\n";
}