백준 1072: 게임 - 이분 탐색, 수학(파이썬)

게임 성공

 

1072번: 게임

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

입력

각 줄에 정수 X와 Y가 주어진다.

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

제한

• 1 ≤ X ≤ 1,000,000,000
• 0 ≤ Y ≤ X

 

내 코드

import sys
x,y=map(int,sys.stdin.readline().split())

if x==y:
    print(-1)
    exit(0)

base=int((y*100)/x) #시작 전의 원래 승률

start=0
end=x

answer=0
isChanged=False #승률 변경 여부를 저장.
while start<=end:
    mid=(start+end)//2

    z=int(((y+mid)*100)/(x+mid))

    if base!=z: #승률이 바꼈으면,
        isChanged=True
        end=mid-1 #더 적은 판 수로도 될 수 있음.
        answer=mid
    else: #승률이 그대로면,
        start=mid+1 #판 수를 늘려야 됨.


if isChanged: #변경 여부가 있으면,
    print(answer) #답 출력
else: #변경 여부가 없으면,
    print(-1) #-1 출력

 

풀이 및 접근)

- 맞게 접근한 것 같았는데 계속 틀렸던 문제이다. 그 이유는 실수의 연산에 있었다.

- 승률을 구하는 과정에서, (y / x) * 100을 했는데, 이렇게 되면 실수 * 100이 되어서 오차가 발생하게 된다.

- 위와 같이 하지않고, (y*100) / x를 해야 비로소 옳은 연산 결과가 나온다.

- 그 외의 부분들은 이분 탐색의 아이디어로 풀면 된다. 근데 문제에서 start=0으로 잡는 것이 명확한데, end는 무슨 값으로 잡아야 할지 헷갈렸다. 그래서 일단 무작정 end=x로 했는데 정답이었다.

- 한가지 신경써야 할 부분은, 변경이 이루어졌는지의 여부를 알고 있어야 한다. 변경이 되지 않았으면 -1을 출력하도록 한다.