[백준] 1072(파이썬) 게임

1072번 게임
이분탐색 문제이다.

아직 이분 탐색이 익숙하지 않아서, 문제를 보자마자 직관적으로 떠오르는 것은 없었다.
문제를 보면서 처음에 들은 생각은 게임횟수-이긴게임 사이의 수가 결국 정답으로 나온다는 것이다.
그래서 든 생각은 게임횟수-이긴게임을 lower_bound로 구현하면, 그것이 정답이라고 생각했다.
그래서 만든 코드가 아래와 같다.

import sys
input=sys.stdin.readline

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

lst=list(range(x-y+1))

def lower(start, end,init_per,lst):
    while start<=end:
        mid=(start+end)//2

        if ((y+mid)*100)//(x+mid) > init_per:
            a=mid
            end=mid-1
        else:
            start=mid+1
    return end

if z>=99:
    print(-1)
else:
    print(lower(0,lst[-1],z,lst))

하지만 이 문제의 메모리는 128mb이고, X의 범위는 1부터 10억이다.
따라서 128mb=128 x 1000kb=128 x 1000 x 1000b=123000000b로 int는 4바이트이니 메모리 초과가 발생하게 된다.(원래는 1024인데 대충 1000으로 잡고 계산한다.)
따라서 배열을 사용하지 않아야 한다.

그렇게 생각한게 결국 로직은 lower_bound 그래도 사용하되, 주어진 수의 범위를 그대로 이용해서 문제를 풀어본다.

import sys
input=sys.stdin.readline

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

if z>=99:
    print(-1)
else:
    #범위를 아예 총 게임 횟수로 잡아버린다.
    start=1
    end=1000000000
    ans=0


    while start <= end:
        mid=(start+end)//2
		
        #기존 승률보다 크면, 그때 mid값은 더해야되는 최소 판수 일 수 있다.
        if (y+mid)*100//(x+mid) >z:
            end=mid-1
            ans=mid
        else:
            start=mid+1
    print(ans)

이처럼 풀면, 10억의 범위의 수에서 탐색을 하게되고, 리스트를 쓰지 않았기 때문에 메모리 초과의 걱정도 없다.
이분탐색은 아직 어렵지만 나름 재미있는 알고리즘인것 같다. 화이팅 해보자.