https://www.acmicpc.net/problem/1072
문제
> 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다.
> 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다.
> 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다.
> 의심을 피했다고 생각한 형택이는 다시 게임을 켰다.
> 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
> 이제 형택이는 앞으로의 모든 게임에서 지지 않는다.
> 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
> 게임 기록은 다음과 같이 생겼다.
1. 게임 횟수 : X
2. 이긴 게임 : Y (Z%)
3. Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
> X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.접근
이분탐색을 통해 승률이 변화가능한 게임수를 탐색한다.
left right의 범위를 게임수의 최소, 최대 값으로 주고 이분탐색을 한다.
중간값을 구해서 그 값을 게임수로 새로 승률을 계산했을 때,
기존 승률보다 높게 나왔다면 그만큼의 게임수로 충분히 승률을 바꿀수 있다는 뜻이므로 이를 다시 right값으로 가지고 이분탐색을 진행한다. 승률을 바꾸기 위한 최소값을 찾는과정이다.
만약 승률이 바뀌지 않았다면 그 게임수로도 승률이 안바뀐다는 뜻이므로 더 많은수의 게임을 해야한다. 즉, left값이 mid+1값으로 갱신되고 탐색을 다시한다.
이 과정을 계속하다 범위가 역전이 나면 직전에 탐색헀던 mid값이 승률을 바꿀수 있는 최소 게임수가 된다.
문제해결
> 게임수, 이긴횟수 를 입력받고 승률을 계산해준다.
문제에 승률이 바뀔수 없는경우는 -1을 출력하라고 했으므로 이를 정의해준다.
> 승률이 100%면 무조건 이긴다고했으므로 더 오를수가 없어서 안되고, 99퍼면 이미 진 게임이 있기 때문에 몇판을 이겨도 100퍼는 될 수 없다. 따라서 99퍼 이상이면 -1을 출력한다.
> 재귀를 통해 게임수의 범위를 줄여나간다. 처음에 최소 게임수 1과 최대 게임수 1,000,000,000을 넣고 rst는 결과로 나올 중간값을 저장하는건데 처음엔 모르고, 아직 게임을 안했므로 0을 넣고 재귀한다.
> 탈출조건 역전을 설정하는데 여기서 탈출되면 rst엔 직전에 저장됐던 rst값이 있으므로 문제없이 만족한다.
> 이분탐색을 한다. mid값을 구하고 그 mid값을 게임수로 해서 새로운 승률을 구한다.
> 승률이 기존보다 크면 mid-1값을 right로 가져 재귀로 새로 탐색하고 작거나 같으면 mid+1을 left로 새로탐색한다.
작거나 같을 땐, 승률을 높일 수 있는 게임수가 아직 못구한것이므로 rst에 mid값이 아닌 그대로 직전의 rst값을 받아간다.코드
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long X, Y, Z;
long long Max = 1000000000;
long long Game(long long left, long long right, int rst)
{
if (left > right) return rst;
long long mid = (left + right) / 2;
long long newZ = (Y + mid) * 100 / (X + mid);
if (newZ > Z)
return Game(left, mid - 1, mid);
if (newZ <= Z)
return Game(mid + 1, right, rst);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> X >> Y;
Z = Y * 100 / X;
if (Z >= 99)
{
cout << -1 << '\n';
return 0;
}
cout << Game(1, Max, 0) << '\n';
}
후기
보통 주어진 수를 가지고 특정 범위에서 mid를 구해 이분탐색하는건 해봤지만 이런방식은 해보지 않아 왜 이게 이분탐색을 쓰는문제인지 했다.
풀이를 공부하고 나니 가능한 모든 범위를 이분탐색으로 줄여가며 조건에 맞춘다라는 방식으로 이분탐색이었다.
같은 알고리즘도 여러 활용이 있다는걸 알았고, 이해하는데 좀 어려웠지만 좋은 방식이었다.
