[C++] 알고스팟/이분법 - 승률 올리기

문제 링크

https://algospot.com/judge/problem/read/RATIO

algospot.com :: RATIO

 

전체 플레이한 게임 횟수 n번에서 이긴 횟수 m번이 주어졌을때 승률 1%를 올리기 위해 최소 몇 번의 게임을 더 플레이해야 하는지에 대한 문제로 최대 플레이 횟수는 20억번으로 주어졌기 때문에 이분 검색을 통해 중간 값을 찾아가며 최소 플레이 횟수를 찾아야 하는 문제입니다.

 

초기 예외처리를 해주고 이분법을 진행합니다.

문제에서 게임을 플레이 할 수 있는 최대 횟수가 20억번 입니다.

그러므로 현재 플레이한 횟수에서 20억번 게임을 연승해도 승률이 오르지 않는 경우 -1을 출력해줍니다.

 

 

구현 코드

 

	#include <iostream>
	using namespace std;
	//주어진 최대 게임수
	long long MAX = 2000000000;
	//플레이한 게임 횟수 b에서 a번 승리했을 때의 승률
	int ratio(long long b, long long a){
	return (a * 100) / b;
	}
	//이분법
	int neededGames(long long games, long long won){
	//현재 승률과 최대 게임수만큼 플레이 했을 때의 승률이 같으면
	//즉, 20억번 연속으로 승리를 해도 1%가 오르지 않았기 때문에 -1을 반환
	if(ratio(games,won) == ratio(games+MAX,won+MAX))
	return -1;
	long long low = 0, high = MAX;
	while(low+1 < high){
	long long mid = (low + high) / 2;
	//mid번 게임을 연속으로 승리를 해도 승률이 오르지 않는다면 low를 mid로 올려줍니다
	if(ratio(games, won) == ratio(games+mid, won+mid))
	low = mid;
	//승률이 올랐다면 high를 mid로 낮춰줍니다
	else
	high = mid;
	}
	return high;
	}
	int main(){
	int test_case;
	long long n,m;
	cin >> test_case;
	while(test_case--){
	cin >> n >> m;
	cout << neededGames(n,m) << endl;
	}
	}

view raw ratio.cpp hosted with ❤ by GitHub