[백준-Python] 게임 : 1072번

🥈 Silver2

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

 

❎ 1차시도

import sys
input=sys.stdin.readline

n,m=map(int,input().strip().split())

if n==m:
    print(-1)
else:
    z=int(m/n*100) # 승률 Z 
    
    start=1
    end=n
    
    result=0
    while start<=end:
        mid=(start+end)//2
        new_z=int((m+mid)/(n+mid)*100)
        if z+1<=new_z: #오른쪽 탐색
            result=mid
            end=mid-1
        else:
            start=mid+1
    print(result)

 

오답의 원인은 잘못 정의한 승률과 절대 변하지 않는 승률일때 -1을 출력하는 조건문이였다.

절대 승률이 변하지 않는 경우는 100%이기 때문에 게임횟수와 이긴게임이 같을때라는 조건으로 작성하였다.

 

❗️ 근데 간과한점이 있다.

승률 99% 또한 100%를 만들 수 없다. 

99.999%라고 하더라도 단 한번이라도 게임을 이미 졌기 때문에 절대 100%를 만들수 없어 승률이 변할수가 없다.

 

end의 값의 범위를 어떻게 지정해야할지 아직 이분탐색이 익숙치 않아 망설였는데

1%만 승률을 올리면 되기 때문에,  최대한 가능성을 열어두고 처음 주어진 게임횟수로 지정하였다.

 

✅ 정답풀이

import sys
input=sys.stdin.readline

n,m=map(int,input().strip().split())
z = m * 100 // n # 현재 승률 


if z >= 99:
    print(-1)
else:
    
    
    start=1
    end=n
    
    result=0
    while start<=end:
        mid=(start+end)//2
        new_z = (m + mid) * 100 // (n + mid)
        if z+1<=new_z: #오른쪽 탐색
            result=mid
            end=mid-1
        else:
            start=mid+1
    print(result)

 

✓ 함수로 변경

import sys

def binary_search(n,m,z):
    if z >= 99:
        return -1

    start = 1
    end = n

    result = 0
    while start <= end:
        mid = (start + end) // 2
        new_z = (m + mid) * 100 // (n + mid)
        if z + 1 <= new_z:  # 오른쪽 탐색
            result = mid
            end = mid - 1
        else:
            start = mid + 1
    return result


def read_input():
    input = sys.stdin.readline
    n,m=map(int,input().strip().split())
    z = m * 100 // n  # 현재 승률
    return n,m,z

def main():
    n,m,z = read_input()
    result = binary_search(n,m,z)
    print(result)

if __name__ == "__main__":
    main()

메모리	실행시간
31120	48