1072번: 게임
각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다.
www.acmicpc.net
입력되는 숫자가 1~10억까지이므로 하나하나 검사하면 시간초과가 날 것이 분명하기 때문에 이분탐색을 이용해 풀었다.
충분히 큰 숫자(30억?)부터 시작해 이분탐색으로 더하기 전과 더한 후와 퍼센트가 일치하는 middle 구간을 찾고, 그 구간을 시작으로 1씩 더해가면서 퍼센트가 변하는 middle값을 찾으면 그 값이 정답이 된다.
추가적으로 입력받은 값의 승률이 99퍼센트 이상이면 아무리 더해도 100퍼센트가 나올 수 없기 때문에 불가능(-1)을 리턴 해주었다.
|
#include <iostream>
using namespace std;
const long long MAX = 3000000000;
long long X, Y;
long long Solution()
{
int winRate = (Y * 100) / X;
if (winRate >= 99) return -1;
long long start = 0, end = MAX;
int result = -1;
while (start <= end)
{
long long middle = (start + end) / 2;
int tempWinRate = ((Y + middle) * 100) / (X + middle);
if (tempWinRate == winRate)
{
result = middle + 1;
start = middle + 1;
}
else
end = middle - 1;
}
return result;
}
int main(void)
{
cin >> X >> Y;
cout << Solution() << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 22day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1062번: 가르침 (0) | 2020.04.29 |
|---|---|
| 백준 6679번: 싱기한 네자리 숫자 (0) | 2020.04.28 |
| 백준 7453번: 합이 0인 네 정수 (0) | 2020.04.26 |
| 백준 1038번: 감소하는 수 (0) | 2020.04.25 |
| 백준 1051번 : 숫자 정사각형 (0) | 2020.04.24 |