[백준_파이썬] [🥈3] 1072번(게임)

 

난이도 : 실버 3

알고리즘 유형 : 이분 탐색 

문제 링크 : https://www.acmicpc.net/problem/1072

반응형

문제 풀이과정

X가 큰 값 범위를 가지고 있으므로, 큰 값이 주어졌을때 X와 Y에 값을 더해가면서 찾는 것은 시간초과에 걸릴 가능성이 높고, 실제로 시간초과에 걸렸다.

이때 시간초과를 막기 위한 탐색법은 여러가지가 있는데, 이분탐색을 이용하는 것도 방법이다. 

이분탐색을 사용할때 유의할 점은 조건을 수행해가며 새 중간값을 지정할때 유의해야 한다는 것이 있다. 이분탐색이 아직 익숙하지 않다면 while문 속에서 밤새도록 돌아가는 코드를 볼 수 있다.

그리고 이 문제는 결과적으로 분모와 분자에 +1을 더해가며 1%가 늘어나는 최소 횟수를 구하는 것이기에

 

1. 이분탐색 과정에서 중간값이 아니라 끝이나 시작값을 찾는다.
2. 부동소수점 오차에 대해 주의를 기울인다.
3. 소수점 이하 값을 버리기 때문에 퍼센트가 99 이상인 경우는 -1 판정한다.

를 주의하면 풀 수 있다. 나는 소수점 처리에선 decimal을 사용하여 풀었다.

그리고 3번에 대해 다소 근시안적으로 접근하여 단순히 X == Y 를 -1 출력하였지만, 그것 뿐만 아니라 Z >= 99인 범위에서 -1을 출력하는 것이 옳았던 것이다.

이는 무한히 게임이 지속된다고 가정해보면 Z = 0인 케이스도 Z = 99 까지 진행되나 X와 Y가 차이를 갖는 지점에서는 절대로 Z가 100이 될 수 없기 때문이다.

---

import decimal
import math

def binary_search(price, target):
    start = 1
    end = price
    while start != end:
        mid = (start+end) // 2
        YY = Y + mid
        XX = X + mid
        ZZ = math.floor(decimal.Decimal(YY*100/XX))
        if target > ZZ:
            start = mid + 1
        elif target <= ZZ:
            end = mid
    return end

X, Y = map(int, input().split())
Z = math.floor(decimal.Decimal(Y*100/X))
Z1 = Z+1
cnt = 0
if Z >= 99:
    print(-1)
else:
    print(binary_search(X, Z1))

 

 

 

---