[백준알고리즘] 1072번: 게임 -Python

[백준알고리즘] 1072번: 게임 -Python

https://www.acmicpc.net/problem/1072

1072번: 게임

이분 탐색 문제이다.

 

주의해야 할 점은 입력이 한 줄만 주어지는 게 아니다. 입력에 각 줄에 대하여 X와 Y가 정해져 있다 했고, 한 줄만 입력된다는 언급이 없었다. 이 부분 때문에 고생했다..

그리고 하나 더 주의해야 할 점은 메모리에 대한 것이다. X, Y의 범위가 굉장히 넓기 때문에 연산 과정 중에서 문제가 일어나기 쉽다. 계속 실패했던 부분이 코드 부분에 있는 'y*100/x' 부분이다. 이 부분들을 'y/x*100'과 같이 100을 나중에 곱해주고 먼저 나눠준다면 정확한 값이 안 나온다.

# 메모리 문제라면 아래의 입력이 주어졌을 때 1을 출력할 수도 있다.

Input:
50 29

Output:
2

 

이분 탐색으로 풀기 전에는 수학으로 공식을 세워서 풀어보려 했는데 y/x*100과 (y+k)/(x+k)*100의 차가 정확히 1 이상이 나는 것도 아니기 때문에 고민했었다.

 

다행히 x의 범위가 부담스럽게 컸기 때문에 이분 탐색인가 싶었다. 자릿수만 주의해주면 괜찮았을 것 같다..

 

while True:
    try: x, y = map(int, input().split())
    except EOFError: break
    now_z = int(y*100/x)
    
    s, e = 1, 1000000000
    while s < e:
        m = (s+e)//2
        mv = int((y+m)*100/(x+m))
        if mv <= now_z:
            s = m+1
        else:
            e = m

    print(e if int((y+e)/(x+e)*100) > now_z else -1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다