이번에는 백준 1072번 게임 문제를 풀어보았습니다.
앞으로 진행하는 모든 게임에서 승리한다고 했을 때, 현재 승률 Z가 처음으로 변하는 시점을 구하는 문제입니다.
추가 게임 횟수가 늘어날수록 승률은 감소하지 않기 때문에, 이분 탐색을 이용하여 승률이 처음 변하는 최소 게임 횟수를 찾았습니다.
문제 설명
현재까지
게임 횟수 : X
이긴 게임 : Y라고 할 때 승률 Z는
Z = (100 * Y) / X로 계산합니다.
정수 나눗셈이므로 소수점 이하는 버립니다.
앞으로 하는 게임은 모두 이긴다고 했을 때, 몇 게임을 추가해야 현재 승률 Z가 달라지는지 구해야 합니다.
만약 아무리 게임을 더 해도 승률이 변하지 않는다면 -1을 출력합니다.
풀이 아이디어
추가로 num개의 게임을 모두 이긴다고 하면
전체 게임 수 = X + num
승리 게임 수 = Y + num이 됩니다.
따라서 새로운 승률은
100 * (Y + num) / (X + num)입니다.
이 값이 기존 승률 Z와 달라지는 최소 num을 찾으면 됩니다.
추가 게임 수가 적을 때는 승률이 그대로이다가, 어느 순간부터 승률이 증가합니다.
즉,
변하지 않음 변하지 않음 변하지 않음 변함 변함 변함 ...과 같은 단조성을 가지므로 이분 탐색을 사용할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
long long int X,Y,Z, ret=-1;
bool check(long long int num){
return ((100 * (Y + num)) / (X+num)) != Z;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> X >> Y;
Z = (100 * Y) / X;
int high = X, low = 1, mid;
while(low <= high) {
mid = (high + low) / 2;
if (check(mid)) {
ret = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ret << '\n';
return 0;
}풀이 흐름
-
현재 게임 횟수
X와 승리 횟수Y를 입력받습니다. -
현재 승률
Z를 계산합니다. -
추가 게임 횟수의 탐색 범위를
1 ~ X로 설정합니다. -
중간값
mid만큼 게임을 추가로 진행한다고 가정합니다. -
check(mid)를 통해 새로운 승률이 기존Z와 달라지는지 확인합니다. -
승률이 변한다면 현재
mid를 정답 후보로 저장하고 더 작은 값을 탐색합니다. -
아직 승률이 변하지 않는다면 더 많은 게임이 필요하므로 오른쪽 구간을 탐색합니다.
-
가능한 값이 한 번도 나오지 않았다면 초기값인
-1이 출력됩니다.
구현 포인트
1. 현재 승률 계산
Z = (100 * Y) / X;현재 승률을 정수 연산으로 계산합니다.
문제에서 소수점 이하는 버린다고 했으므로 별도의 실수 연산이 필요하지 않습니다.
예를 들어
X = 53
Y = 47이라면
4700 / 53 = 88이므로 승률은 88%가 됩니다.
2. 추가 게임을 모두 이긴 경우
추가로 num판을 진행하고 모두 승리한다면
X → X + num
Y → Y + num이 됩니다.
따라서 새로운 승률은
(100 * (Y + num)) / (X + num)으로 계산할 수 있습니다.
3. 승률이 변하는지 확인
bool check(long long int num){
return ((100 * (Y + num)) / (X+num)) != Z;
}check()는 num판을 추가로 이겼을 때 승률이 기존 Z에서 변하는지 확인합니다.
승률이 다르다면
true아직 같다면
false를 반환합니다.
4. 이분 탐색 범위
int high = X, low = 1, mid;최소 한 판은 더 해야 하므로 low = 1로 시작합니다.
상한은 현재 게임 횟수인 X로 설정하였습니다.
이 범위 안에서 승률이 변하는 최소 추가 게임 횟수를 탐색합니다.
5. 승률이 변하는 경우
if (check(mid)) {
ret = mid;
high = mid - 1;
}mid판을 추가했을 때 승률이 변한다면 현재 mid는 가능한 정답입니다.
하지만 더 적은 게임만으로도 승률을 바꿀 수 있을 수 있으므로 왼쪽 구간을 계속 확인합니다.
따라서
high = mid - 1;로 탐색 범위를 줄입니다.
6. 승률이 변하지 않는 경우
else {
low = mid + 1;
}현재 mid만큼 게임을 추가해도 승률이 그대로라면 더 많은 게임을 해야 합니다.
따라서 오른쪽 구간을 탐색합니다.
7. 이분 탐색이 가능한 이유
추가 게임은 전부 승리하기 때문에 게임을 더 진행할수록 승률은 떨어지지 않습니다.
어떤 num에서 처음 승률이 변했다면 그보다 더 많은 게임을 승리했을 때 다시 원래 승률로 돌아가는 일은 없습니다.
따라서 check(num)의 결과는 다음과 같은 형태를 가집니다.
false false false false true true true ...즉, 처음으로 true가 되는 위치를 찾는 문제이므로 이분 탐색을 사용할 수 있습니다.
8. 승률이 절대 변하지 않는 경우
long long int X,Y,Z, ret=-1;정답 변수 ret을 처음부터 -1로 설정합니다.
이분 탐색을 진행하면서 승률이 변하는 경우가 발견되면
ret = mid;로 갱신합니다.
반대로 끝까지 가능한 mid가 없다면 ret은 그대로 -1이므로 이를 출력합니다.
특히 현재 승률이 매우 높은 경우에는 앞으로 모든 게임을 이겨도 정수 승률이 증가하지 않을 수 있습니다.
9. long long을 사용하는 이유
X와 Y는 최대 1,000,000,000입니다.
승률 계산 과정에서
100 * Y를 수행하면 최대
100,000,000,000까지 커질 수 있습니다.
이는 int 범위를 넘어가기 때문에 X, Y, Z를 long long으로 선언하였습니다.
long long int X,Y,Z, ret=-1;check()의 계산 역시 long long 범위에서 처리됩니다.
시간복잡도
check()는 단순한 산술 연산만 수행하므로
O(1)입니다.
이분 탐색은 1 ~ X 범위에서 수행되므로
O(log X)번 반복됩니다.
따라서 전체 시간복잡도는
O(log X)입니다.
X가 최대 1,000,000,000이어도 매우 빠르게 해결할 수 있습니다.
