[Python, 이분탐색] 백준 1072 게임
·
Algorithm
접근방식이 문제를 해결하기 위해 이진 검색을 사용합니다. 중요한 점은 'X'의 가능한 값이 크기 때문에 간단한 계산이 비효율적이라는 것이다. 따라서 이진 검색을 사용하여 승률을 높이는 데 필요한 최소 추가 게임 수를 효율적으로 결정할 수 있다.문제풀이초기 승률 Z = (100 * Y) // X를 계산합니다.Z >= 99인 경우 백분율을 더 높이는 것은 불가능하며 -1을 반환왼쪽 = 0 및 오른쪽 = X로 시작중간점 계산: mid = (왼쪽 + 오른쪽) // 2.새로운 승률 (100 * (Y + mid)) // (X + mid)가 Z를 초과하는 경우 결과를 mid로 업데이트하고 검색 범위를 왼쪽으로 조정(right = mid - 1).그렇지 않으면 검색 범위를 오른쪽(왼쪽 = 중간 + 1)으로 조정합니다...