백준 - 1072 게임 [이분탐색]

1072 게임

1. 문제유형

• Binary Search

2. 자료구조

1. 중요한 점은 y/x * 100과 같이 실수형으로 계산 후 int로 바꿔줄 시 정확하지 않을 수 있다.
2. 따라서 실수형 계산이 아닌, y * 100//x처럼 정수형 계산으로 바꿔 승률을 계산해야 한다.

• z (int): 초기 승리한 게임 수 y/전체 게임 수 x * 100
• target (int): 승리한 경기수를 이분탐색하며 계산한 승률
• left (int): 더해나갈 승리한 횟수의 최소값
• right (int): 더해나갈 승리한 횟수의 최대값
• mid (int): (left+right)//2 == 중간값으로 실제 더할 승리한 횟수

3. 해결과정

1. 승리한 게임 수를 찾는 게 핵심이며, 범위는 0부터 x(10 ** 9)까지이다.
2. 따라서 1부터 적용할 경우 10억 번 연산이 필요하므로 이분탐색을 사용한다.
3. x,y에 mid를 더한 후 승률을 계산한다.
4. 승률이 초기 승률값과 같다면 left = mid+1
5. 승률이 초기 승률값보다 크다면 answer=mid 후 right = mid-1
6. 3-5를 left <= right일 동안 반복한다.
7. 반복이 끝난 후 승률이 초기값과 같다면 -1을, 아니라면 answer를 출력한다.

x, y = map(int, input().split())
left, right = 0, x
answer = 0
z = y*100//x

while left<=right:
    mid = (left+right)//2
    game = x + mid
    win = y + mid
    target = win*100//game

    if z == target:
        left = mid + 1
    else:
        answer = mid
        right = mid - 1

x, y = x+answer, y+answer
result = y*100//x
if result == z:
    print(-1)
else: 
    print(answer)