백준 1072번 게임

< 백준 1072번 게임 - 마포 코딩박 >

사용한 알고리즘: 수학


 현재까지의 게임 횟수와 이긴 횟수 가 주어지고, 앞으로는 모두 이긴다고 가정했을 때, 몇판을 더 해야 승률이 증가하는지 구하는 문제였습니다.

풀이는 다음과 같습니다.
(1)
 X: 전체판수, Y: 이긴횟수, Z: 승률이라고 하면, Z = 100*(Y/X) 입니다.
 승률이 Z+1 이 되기 위한 추가 판수를 K 라 하면, Z+1 = 100*(Y+K/X+K) 입니다.
 따라서 K = ((Z+1)*X - 100*Y)/(99-Z) 입니다.

 주의할 점은, Z를 계산할 때 Y/X*100 이라고 하면 안된고 100*Y/X라고 해야합니다.
 (정확한 이유는... 모르겠습니다.)
 또한 Z 가 이미 99 프로 이상이면, 100프로를 만들기는 불가합니다.

	#include <bits/stdc++.h>
	using namespace std;
	double X, Y;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> X >> Y;
	// Y/X*100 은 안된다.
	double Z = floor(100*Y/X);
	if(Z>=(double)99) cout << -1 << '\n';
	else{
	int ans = (int)ceil((X*Z+X-100*Y)/(99-Z));
	cout << ans << '\n';
	}
	return 0;
	}

view raw BOJ 1072.cpp hosted with ❤ by GitHub