2022-07-05 @이영훈
접근 방법
이 문제는 이진탐색으로 접근해야 한다. 문제 조건에서 X가 10억까지 갈 수 있기 때문에, 선형적으로 문제를 풀면 시간초과가 됩니다.
•
코딩 테스트 환경에서 파이썬은 1초에 2,000만 ~ 1억번 정도의 연산을 처리할 수 있습니다.
•
따라서 이진탐색으로 O(logN)으로 풀어야 시간 내에 풀 수 있습니다.
start를 0으로 잡고 end를 게임 플레이 횟수와 동일한 x로 초기화합니다.
middle은 추가로 플레이한 횟수이자 추가로 승리한 횟수입니다. (문제 조건에서 새로 경기한 게임은 모두 이긴다라고 했습니다)
그리고 이진탐색 알고리즘으로 새로 갱신된 승률 new_z가 기존 승률 z랑 다른지 (또는 더 큰 지) 확인하고 그렇다면 answer에 기록하고, 더 적게 게임하고 이길수도 있으니 end = middle -1 로 두고 계속 탐색을 이어간다.
파이썬 코드
import sys
input = sys.stdin.readline
x, y = map(int, input().split())
z = int(100 * y / x)
start = 0
end = x
answer = -1
while start <= end:
middle = (start + end) // 2
new_z = int(100 * (y + middle) / (x + middle))
if new_z > z:
answer = middle
end = middle - 1
else:
start = middle + 1
print(answer)
Python
복사