[python] 1072 게임

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

1072번: 게임

 

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지출력,  Z가 절대 변하지 않는다면 -1을 출력

 

 

조건 중 Z가 절대 변하지 않을 경우는

X, Y가 같을 때, 즉 Z가 100일때와

승률의 소수점은 버리기 때문에 Z가 99인 경우이다.

+

파이썬에서

int(y / x) * 100 은 부동소수점 오차로 틀렸다고 나옴

z= (y*100)//x  100먼저 곱해 줘야한다.

 

수학공식

원래 이진탐색 문제라는데 저는 수학공식으로 풀었습니다.

# a는 이겨야 하는 게임 수
# z+1 = (y+a)*100 / (x+a)     x, y, z에는 입력받은 수가 들어가기 때문에 a구할 수 있음!

from math import *
x,y= map(int,input().split())

if 1<= x and x <= 1000000000 and 0<=y and y <= x:
  z= (y*100)//x 
#a는 이겨야 하는 게임 수
#z+1 = (y+a)*100 / (x+a) 
  if z==100 or z==99:
    print(-1)
  else:
    #a =((z+1)*x/100-y)/(1-(z+1)/100) 여기까지 하면 틀렸다고 나옴.. 이유아시는분 알려주세요ㅠㅠ
    a =(((1+z)*x)- (100*y))/(99-z)
    print(ceil(a))

 

이진탐색(이분탐색)

이진탐색으로 푸는 방법도 검색해서 공부했어요!!

이긴게임 수(a)를 z가 변할때 까지 while문으로 1씩 증가하면서 확인하는 방법을 개선

처음에 a를 중간값 부터 넣어어서

if문에서 확률을 구하여 보고

확률이 z보다 작으면 a가 더 커져야 하니깐 이전에 a였던 mid까지 값을 버리고 mid+1 ~ right영역

확률이 z보다 크면 a에 mid를 넣지만 최소 게임수를 구하는 것이기 때문에 right영역을 줄여가며 a의 최소값을 찾음

x, y = map(int, input().split())
z = (y * 100) // x
if z >= 99:
    print(-1)
else:
    a = 0
    left = 1
    right = X
 
    while left <= right:
        mid = (left + right) // 2
        if (y+mid)*100 // (x+mid) <= z:
            left = mid+1
        else:
            a = mid
            right = mid - 1
 
    print(a)