[Algorithm] 백준_1072번: 게임

오늘의 문제는 🚀 백준 1072 게임이다.

input이 십억이다… 이럴때는 무조건 이분 탐색으로 풀어야한다.

테스트케이스 이해하기

형택이는 앞으로 절대 지지 않는다. 그럴 경우 승률이 바뀌는 최소 값을 찾는게 이번 문제!!

알고리즘

1. start와 end 값을 설정해준다.

2. 현재 승률을 구하고 99와 같거나 크면 -1를 프린트 해주고 끝낸다.

   (이미 틀린 경우가 있기 때문에 승률이 100이 될 수는 없음)

3. start가 end보다 커지기 전까지 while문을 돈다.

4. start와 end의 중간값을 더해서 계산한 승률을 현재 승률과 비교해서 크면 end의 범위를 줄이고 작으면 start의 범위를 줄인다.

5. while문을 탈출하고 시작점을 프린트해준다.

p.s 진짜 왕창 틀렸다.. 파이썬은 곱하기,나누기 하는 순서에 따라서 결과값이 달라진다. int()도 함부로 쓰면 안된다.

정답코드

all, win = map(int, input().split())

start = 0
end = 1000000000
firstwinRate= (win*100//all)

if 99 <= firstwinRate:
    print(-1)
else:
    while(start <= end):
        mid = (start + end)//2
        # print(start, end, mid)
        winRate = (win+mid)*100//(all+mid)
        if winRate > firstwinRate:
            end = mid - 1

        else:
            start= mid +1

    print(start)

🚀Reference: 백준 1072 게임