• 백준 1072번 게임 :: 마이구미
    알고리즘 풀이/이진 탐색 2016. 12. 27. 23:55
    반응형

    이번 글은 백준 알고리즘 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

    반응형

    댓글 2

Designed by Tistory.