[BOJ] Python 백준 게임(1072)

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

 

수학적 풀이

# https://www.acmicpc.net/problem/1072
import sys
import math
input = sys.stdin.readline

X, Y = map(int,input().split())
check = (Y * 100) // X

if check>=99:
  print(-1)

else:
    check += 1
    k = ((check*X)-(100*Y)) / (100-check)
    result = math.ceil(k)

    print(result)

 

결국 1%만 늘어도 변화가 일어나는 것이기에 현재 승률에 1%를 더한 값으로 몇게임이 더 늘어나야하는지에 대한 기본 방정식을 세워 줬다.

 

하지만, 4%에서 계속 틀렸고 이는 파이썬 부동소수점에 대한 문제로 조건문을 통과하지 못했었다.

math.ceil로 소수점이 존재하는 경우 무조건 올림 할 수 있도록 변경해주었다.

 

 

 

이분 탐색 풀이

# https://www.acmicpc.net/problem/1072
import sys
input = sys.stdin.readline

X, Y = map(int,input().split())
check = (Y * 100) // X
start = 0
end = X
result = X
if check>=99:
  print(-1)

else:
    while start <= end:
        middle = (start+end)//2

        if (100 * (Y+middle)) // (X+middle) > check:
            result = middle
            end = middle - 1

        else:
            start = middle + 1
    print(result)

이분 탐색을 통해

start = 0

end = 1%만 올려도 됌으로 X 이상일 수 없음

 

- 게임을 중간값 만큼 더한 것이 check보다 월등히 크면 중간값으로 끝점을 다시 잡는다

- 게임을 중간값 만큼 더한 것이 check보다 월등히 작다면 중간값으로 시작점을 다시 잡는다

 

위 조건을 반복하여 start가 end값과 같아지거나 커지면 이분 탐색 종료