- 처음에 플레이한 게임횟수와 현재까지 이긴 게임의 수를 입력으로 받음.
- 이 후부터 플레이한 게임은 반드시 이긴다.
- 게임기록은 삭제할 수 없음.
[ 입력 ]
- 각 줄에 게임을 플레이한 총 횟수 ( X ), 현재까지 이긴 게임 횟수 ( Y ) 입력.
[ 입력범위제한 ]
- 1 ≤ X ≤ 1,000,000,000
- 0 ≤ Y ≤ X
[ 출력 ]
- 형택이가 승률을 올리기 위해 플레이해야하는 최소한의 게임 수 출력.
- 만약 승률 ( Z ) 가 절대 변하지 않는 경우라면 -1 출력
이번 문제는 2가지 방법으로 풀 수 있다.
1) 승률이 변하는 판수를 수식으로 풀어서 구현
2) 플레이하는 판수를 변경해가며 매번 직접 승률을 구해보는 방법
이렇게 두가지 방법 중 나는 2번째 방법으로 해결했다.
2번째 방법으로 구현할 때 1부터 최대값인 1,000,000,000 까지 일일히 대입하다보면 당연히 시간초과가 난다.
그래서 하나씩 대입하는 것이 아닌 이진탐색을 사용해서 값을 구하려고 한다.
- 이진탐색에 대한 내용은 아래 링크에 정리해놨다!
https://velog.io/@jmink002/Binary-Search
이 문제에 이진탐색을 적용해 문제를 해결하는 과정은 다음과 같다.
- 입력받은 x 와 y 값을 가지고 z 를 먼저 구한다.
- 1에서 구한 z 가 99 % 이상이면 -1을 출력 후 프로그램을 종료한다.
( ∵ 승률의 소숫점은 반올림이 아닌 버림이며, 앞으로 플레이하는 게임은 무조건 승리한다.)- 2의 조건을 만족하지 못하는 경우, 이진탐색으로 최적의 값을 찾는다.
( 여기서 최적의 값이란 승률을 올리기 위해 플레이해야하는 최소한의 게임 수)- left = 0, right = 1,000,000,000 으로 놓은 후, 이것의 중앙값 ( mid ) 를 앞으로 플레이할 게임의 수로 놓고 newz 를 계산한다.
- 즉, newz = 100 * (y + mid) / (x + mid) 이다.
- 그 후 newz 와 z 를 비교해 탐색범위를 줄여가며 최적의 값을 찾는다.
- 탐색범위는 다음의 2가지 경우로 나눠 조정한다.
- z < newz 인 경우 : mid 를 기준으로 왼쪽 범위로 조정
=> 최소 판수를 구해야하니 플레이할 판수를 줄인다.
=> right = mid - 1 로 변경 후 다시 계산- z == newz 인 경우 : mid 를 기준으로 오른쪽 범위로 조정
=> 현재의 mid 만큼의 게임을 더 하더라도 승률이 바뀌지 않은 것이므로 판수를 더 늘린다.
=> mid 를 증가시켜야하므로 left = mid + 1 로 변경 후 계산
이진탐색이 끝났다면 그때의 left 값을 출력하면 문제 해결!
#include <iostream>
using namespace std;
int calc_rate(long long x, long long y) {
return (100 * y) / x;
}
int main() {
// Declare three variables
// 0 < x <= 1,000,000,000
// => the range of "y" exceed the range of "int"
// So, these variables are declared as the range of "long long"
long long x, y, z;
int count = -1;
// input x and y
// x is total plays
// y is win games
cin >> x >> y;
// calculate z
z = calc_rate(x, y);
// if z >= 99%, then print "-1"
if (z >= 99) {
cout << count << endl;
return 0;
}
// if z <= 99, find result with binary search
int left = 0;
int right = 1000000000;
int mid = 0;
while (left <= right) {
mid = (left + right) / 2;
long long newz = calc_rate(x+mid, y+mid);
// if z < newz, then reduce the number of rounds
if (z < newz) {
right = mid - 1;
}
// else, increase the number of rounds
else {
left = mid + 1;
}
}
// print result
cout << left << endl;
return 0;
}
# calculate z
def calc_rate(x, y):
return (100 * y) // x
# input x, y
x, y = map(int, input().split())
z = calc_rate(x, y)
# if z >= 99 then print "-1"
if z >= 99:
print(-1)
# else find value with binary search
else:
left = 0
right = 1000000000
while (left <= right):
mid = (left + right) // 2
newz = calc_rate(x+mid, y+mid)
# if z < newz then reduce the number of rounds
if (z < newz):
right = mid - 1
# else increase the number of rounds
else:
left = mid + 1
print(left)