[BOJ] [Python] 1072번 : 게임

이진탐색을 이용하여 풀었다.

 

 

이 문제는 주의해야 할 점이 있다.

 

첫 번째,

int(y + mid / (x + mid ) * 100)는 안된다.

(100 * (y + mid)) // (x + mid)는 된다.

 

똑같은 의미인데 .. 왜일까?

 

부동소수점 오차

Python은 부동소수점 오차가 있어서, 정확하지 않다고 한다.

 

(다음부터 풀 때는 이 점을 주의해야겠다!)

 

 

 

두 번째,

입력이 몇 줄인지 정확히 명시하지 않았다.

그러므로 예시처럼 한 줄일거라고 생각하지 말고, N개의 줄에 대비해야 한다.

 

 

 

high 값을 잡기가 애매했다. 그래서 문제에서 명시해준 최대인 10억을 잡았다.

 

def BSearch(x, y, z):
    low = 1
    high = 1000000000

    while low <= high:
        mid = (low + high) // 2
        new_z = (100 * (y + mid)) // (x + mid)

        if new_z > z:
            high = mid - 1

        else:  # new_z == z
            low = mid + 1

    return high + 1


while True:
    try:
        num = list(map(int, input().split()))

    except EOFError:

        break

    i_x = num[0]  # 게임 횟수 10
    i_y = num[1]  # 이긴 게임 8 ( 진 게임 2 )
    i_z = (100 * i_y) // i_x  # 승률

    if i_z > 98:  # 승률 100%
        print(-1)
    else:
        print(BSearch(i_x, i_y, i_z))

 

승률은 99이상이면 바뀌지 않는다.

 

 

+ '틀렸습니다'

 

처음에 low를 현재 승리한 값으로 잡아서 풀었는데, 틀린 이유는 아직 모르겠다.

 

틀린 이유를 찾았다. low 값을 y로 잡았기 때문에, 그에 따라 high 값을 1000000000 + y 로 해줘야 한다.

 

좀 더 생각 볼 문제이다.

def BSearch(x, y, z):
    low = y
    high = 1000000000

    while low <= high:
        mid = (low + high) // 2
        new_z = (100 * mid) // (x + mid - y)

        if new_z > z:
            high = mid - 1

        else:  # new_z == z
            low = mid + 1

    return high + 1


while True:
    try:
        num = list(map(int, input().split()))

    except EOFError:

        break

    i_x = num[0]  # 게임 횟수 10
    i_y = num[1]  # 이긴 게임 8 ( 진 게임 2 )
    i_z = (100 * i_y) // i_x  # 승률

    if i_z > 98:  # 승률 100%
        print(-1)
    else:
        print(BSearch(i_x, i_y, i_z) - i_y)