[Python3] 백준 1072번 게임

사용 언어 - Python3

문제 - 게임

1072번: 게임

 

 

정답

이분 탐색 문제 (정답 맞춘 여부 X)

1. 파이썬에서 소숫점 버린 승률 구하기

(Y//X)*100 파이썬에서 부동소숫점 오차로 오류!

Z = (Y*100)//X 사용!

 

2. 예외 처리

형택이는 앞으로의 모든 게임에서 지지 않기 때문에 x+1, y+1이다.

만약 x==y 라면, x//y=100이고 x+1==y+1이라 Z값이 항상 같다. 절대 변하지 않는다.

z가 99 이상이면 print(-1)을 출력해준다.

 

3. x+1, y+1 을 하면서 count 값을 하나씩 추가하기엔 비효율적이기 때문에 이분 탐색을 사용한다.

구하려는 추가 게임수는 최소 1번부터 최대 x번까지이기 때문에, left=1, right=x, mid = (left+right)//2이다.

x -> x+mid, y -> y+mid 로 바꾸어 계산한 새로운 z 값이 기존 z과 비교했을 때 작거나 같다면, left = mid+1로 범위 업데이트

아닌경우, right = mid-1로 범위 업데이트

answer = mid

 

 

import sys
input = sys.stdin.readline

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

if z >= 99: 
    print(-1)
else:
    answer = 0
    left = 1
    right = x
    
    while left <= right:
        mid = (left+right)//2
        if ((y+mid)*100) // (x+mid) <= z:
            left = mid+1
        else:
            answer = mid
            right = mid -1
    print(answer)

 

 

 

---

레퍼런스

• 정답 참고

[백준 1072] 게임 (python)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부