[python] 백준 1072 - 게임

출처 : 백준, https://www.acmicpc.net/problem/1072

1072번: 게임

 

첫 번째 풀이 : 실패

 

import math

if __name__ == '__main__':
  X, Y = map(int, input().split())
  a = math.ceil(X**2/(99*X-100*Y)) if 99*X-100*Y > 0 else -1
  print(a)

 

공식을 계산할 때, 전과 후의 차가 0.01 이상이 되는 게임 횟수로 설정을 했는데,

생각해보니 0.01이려면 89%와 88% 간의 차이지 88.9% 일 수도 있으니 0.01보다 작을수도 있더라.

 

 

두 번째 풀이 : 성공

 

def binarySearch(X, Y, left, right):
  if (Y / X) >= 0.99:
    return -1
    
  if left >= right:
    return left

  mid = (left + right) // 2
  mid_result = (Y + mid) / (X + mid)

  Z = int((Y*100/X)) + 1
  
  if mid_result*100 >= Z:
    return binarySearch(X, Y, left, mid)
  else:
    return binarySearch(X, Y, mid + 1, right)

if __name__ == '__main__':
  X, Y = map(int, input().split())
  count = binarySearch(X, Y, 1, 1000000000)
  print(count)

 

이분 탐색으로 들어갔다. 일정 범위 내에서 많은 것을 빠르게 탐색하는 것에는 이분 탐색이 빠르다고 생각했기 때문이다.

이분 탐색에서 중요한 것은 범위 설정인데

99%나 100%면 더 이상 올라갈 수 없는 확률이므로 제외하고

가장 큰 수가 주어졌을 때, 98%인 input을 고려하면

 

1000000000 980000000

 

이 있다.

이 경우에 1,000,000,000만큼 더해주어야 99%가 되고

이 수가 더해질 수 있는 수 중 최댓값이므로 1~1,000,000,000까지의 범위에 대해 탐색한다.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

(Y/X)*100 vs (Y*100)/X

 

 

이 문제의 정답률의 원흉이 이 부분인 것 같은데, 가장 대표적으로 언급되는 예시로

 

#input
50 29

 

가 있다.

눈으로 계산해봐도 58/100이라 58%가 나와야하는데 계산 순서에 따라 57.99999999나 58.0이 나온다.

이는 컴퓨터에서 실수를 정확하게 표현할 수 없기 때문이다.

하나의 예시를 더 들면 0.3과 0.6을 더해 0.9와 비교하는 예시가 있다.

 

 

위 경우에도 이상하게도 답변이 False로 나오는데 이는 0.3+0.6을 컴퓨터에서 0.899999999로 계산하기 때문이다.

이는 컴퓨터의 한계이므로 실수 계산을 할 때 주의하여야한다.

 

 

import math

if __name__ == '__main__':
  X, Y = map(int, input().split())
  Z = (100*Y/X) / 100 + 0.01
  a = math.ceil((Z*X-Y)/(1-Z)) if Z < 0.99 else -1
  print(a)

 

고찰

 

수학적으로 풀 수 있을 것 같은데 안 풀리네......