[파이썬] 1072번: 게임 / 브루트포스 이분탐색

---

 

1. 백준 1072번 게임

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

 

 

2. 오늘의 회고

* 정답은 아래에 있습니다.

첫번째 접근: 단순 구현 시간초과

파이썬 소수점 함수

반올림 num = f " {num: .2f} " 소수점 3자리에서 반올림하여 2자리까지 출력

버림 math.floor(num)

올림 math.ceil(num)

 

import math
x,y = map(int, input().split()) 
z = (y/x)*100
z = math.floor(z)
i = 1
if x<=y:
    print(-1)
else:
    if y==0:
        while True:
            z1 = ((y+i)/(x+i))*100
            z1 = math.floor(z1)
            if z1>=1:
                print(i)
                break
            else:
                i = i+1
    else:
        while True:
            z1 = ((y+i)/(x+i))*100
            z1 = math.floor(z1)
            if z1 > z:
                print(i)
                break
            else:
                i = i+1

 

 

두번째 접근: 이분탐색 성공

 

x의 범위가 10억인 것을 보고 탐색범위를 좁혀야 한다는 생각이 필요하다.

얼마를 더할지 1부터 늘려가는 것이 아니라 이분탐색을 이용해 mid를 설정 후 범위를 좁혀가야 한다.

 

* math.floor를 사용해 소수점 버리기

z = (y / x) * 100

z = math.floor(z)

 

* 정수 나눗셈을 사용해 소수점 버리기(당연한 것이였음)

z = (y * 100) // x

 

import math
x,y = map(int, input().split())
z = (y * 100) // x
z = math.floor(z)
i = 0
if z>=99:
    print(-1)
else:
    low, high = 1, 1000000000
    while low<=high:
        mid = (low + high) // 2
        z1 = ((y + mid) * 100) // (x + mid)
        z1 = math.floor(z1)

        if z1 > z:
            i = mid
            high = mid-1
        else:
            low = mid+1
    print(i)

 

이분탐색을 통해 mid의 값을 좁혀가고 z1 (mid값을 더한 새로운 확률) 값이 z (원래 확률) 보다 커지면 i 값을 저장한다. 이 과정을 반복하여 low 값이 high 값과 같거나 커질 경우 while 문을 빠져나온다. 최종적으로 while문을 빠져나올 때 저장된 i 값이 최소 값 ( =  최소 몇 판 더 해야하는지) 이 된다.