[백준] 1072번: 게임 / 파이썬

문제 링크

---

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

풀이 코드

---

x, y = map(int,input().split())
z = y * 100 // x 

left, right = 1, 1000000000
dap = -1

while left <= right:
    mid = (left + right) // 2
    newZ = (y + mid) * 100 // (x + mid)
    if newZ > z:
        dap = mid
        right = mid - 1
    else:
        left = mid + 1

print(dap)

코드 해석

---

이분탐색으로 풀었다.

탐색 범위를 반으로 나눠서 탐색하는것이다.

000100000000 원래 수열

000100 000000 반 나누고 왼쪽 선택

000 100 반 나누고 오른쪽 선택

10 0 반 나누고 왼쪽 선택 

1 0 반 나누고 왼쪽 선택

1

이렇게 찾으면 시간 절약이 훨씬 많이 된다.

 

 

체감 난이도: ★★☆☆☆