백준 / 게임 / 1072번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 게임 / 1072번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/1072

 

문제 설명

---

나의 풀이

if __name__=="__main__":
    x, y = map(int, input().split())

    # 현재 승률 계산
    winning_rate = y * 100 // x

    # 게임 횟수 추가를 위한 초기값
    number_event = 0

    # 이기는 횟수를 늘려가며 확인
    while True:
        if x == y:
            print(-1)
            break

        number_event += 1
        new_winning_rate = (y + number_event) * 100 // (x + number_event)
        
        # 승률이 변하면 출력 후 종료
        if new_winning_rate > winning_rate:
            print(number_event)
            break

단순한 풀이 방법 입니다. 승리하는 게임을 하나씩 늘려서 직접 비교하는 방식을 사용했습니다.

하지만 이 풀이는 게임의 수가 커질수록 비효율적이므로 다른 방법을 사용해야합니다!

if __name__=="__main__":
    x, y = map(int, input().split())

    # 현재 승률 계산
    winning_rate = y * 100 // x

    # 이미 승률이 100%인 경우 더 이상 개선 불가
    if winning_rate >= 99:  # 100% 승률이 사실상 불가능하므로 99로 제한
        print(-1)
    else:
        left, right = 1, x  # 이진 탐색 범위 설정
        answer = -1
        
        while left <= right:
            mid = (left + right) // 2  # 중간값 계산
            new_winning_rate = (y + mid) * 100 // (x + mid)
            
            if new_winning_rate > winning_rate:
                answer = mid
                right = mid - 1  # 더 작은 범위 탐색
            else:
                left = mid + 1  # 더 큰 범위 탐색
        
        print(answer)

이분 탐색을 이용하여 풀이를 사용했습니다 이렇게되면 시간 복잡도는 O(N)에서 O(logN)으로 줄일 수 있게 됩니다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/188

[알고리즘] 이분 탐색(Binary Search)