백준 1072번 게임 :: 마이구미

이번 글은 백준 알고리즘 1072번 "게임" 문제를 다뤄본다.

접근 방식은 이진 탐색으로 해결한다.

이진 탐색 - http://mygumi.tistory.com/72

문제 링크 - https://www.acmicpc.net/problem/1072

게임 기록은 다음과 같이 생겼다.

게임 횟수 : X
이긴 게임 : Y (Z %)
Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 몇 판해야 Z가 변하는지 구하는 프로그램을 작성하시오. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

본인이 처음 접근한 방법을 설명해보겠다.

일단 승률을 구하는 방법이다.

(이긴 게임횟수 / 게임횟수) * 100 이 된다.

int로 형변환 시킴으로써 소수점들을 버리거나 Math.floor를 이용하는 방법이 있다.

문제를 해결하기 위해 먼저 한가지 생각한 건 확률이 99%인 경우는 절대 100%가 될 수 없기에 절대 변하지 않는다.

증명은 해보면 게임횟수와 이긴횟수가 같아야 승률은 100%이라는 걸 알고 있다.
하지만 100 99 가 주어진다하더라도 게임 횟수와 이긴 횟수는 같이 증가하기 때문에 게임횟수와 이긴횟수가 같아질 수가 없다.

101 100 -> 102 101 -> 103 102 -> 104 103

그렇다면 이제 어떻게 접근할 것인지 보자.

먼저 승률을 구한 후 게임횟수와 이긴 게임 횟수를 늘리면서 루프를 통해 승률이 변화 여부를 생각해보았다.

int rate = (int) ((y / x) * 100);
int temp = rate;
int cnt = 0;

while(temp == rate) {
    cnt++;
    temp = (int) ((++y / ++x) * 100);

    if (temp >= 99) {
        cnt = -1;
        break;
    }
}

이렇게 하면 사실상 간단히 해결되는 접근 방식이다.

그래서 별 어려움없이 구현을 할 수 있었다.

하지만 1000000000 980000000 입력이 주어질 경우 승률이 98% -> 99% 변화되기까지 너무 오래 걸리게 되어 시간 초과를 초래한다.

안타깝지만 아예 접근을 바꿔야한다.

주변 글들을 보니 수학으로 접근하여 푼 것들을 볼 수 있었다.

하지만 수학 머리가 딸리는지 도저히 이해가 가지 않았다...

그래서 본인은 이진 탐색으로 해결해보았다.

while(first <= last) {
    mid = (first+last)/2;

    temp = (int) ((y+mid)/(x+mid)*100);

    if (temp > target) {
        last = mid - 1;
    } else {
        first = mid + 1;
    }

}

기본적인 이진 탐색으로 구현하면 충분히 풀 수 있다.

주의할 점은 다른 문제에서도 그렇듯이 늘 변수 타입의 범위를 넘을 수 있다는 점을 주의하자.

하지만 본인은 계속 틀렸다고 나와 시간을 많이 낭비했다..

아직 자세한 이유는 잘 모르겠지만 형변환하면서 문제가 되는 것이 있나보다...

(y/x)*100-> (y*100/x)
(y+mid)/(x+mid)*100) -> (y+mid)*100/(x+mid)

위와 같이 수정하니까 기어코 맞출 수 있었다.....

자세한 이유를 알면 알려준다면 감사하겠다.

아래 소스 링크를 걸어두겠다.

백준 알고리즘 1072번 게임 JAVA 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/binarysearch/1072.java