[알고리즘]백준 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

풀이

---

원래는 이분탐색 문제인데 조금 다른 방식으로 풀이해보았습니다 

 

탐색을 진행할때 1스텝씩 이동을 하게 되면 당연하게도 시간초과에 걸립니다

이런식으로 전체 탐색을 진행해야하는 경우 그냥 과감하게 100스텝 혹은 1000스텝 정도 이동을 하면서

확인을 진행합니다 

이 문제 같은 경우에는 첫번째 반복문의 경우 정수부가 초기 백분율의 정수부와 달라지는 경우 

반복문을 탈출하는데 두번째 반복문을 이용해 다시 스텝을 거꾸로 밟아가줍니다 

1스텝씩 이동하는 경우 시간이 N이라면 N/step크기 +step크기로 문제 해결이 가능합니다  

 

import sys 
from math import floor 
X, Y  = map(int, sys.stdin.readline().strip().split())
start = int((100*Y)/X)
cnt= 0
if int((100*Y)/X)<99:
    while True:
        X= X+100
        Y= Y+100
        cnt+=100
        if start!=int((100*Y)/X):
            break
    while True: 
        X= X-1
        Y= Y-1
        cnt-=1
        if start==int((100*Y)/X):
            break
    print(cnt+1)
else: 
    print(-1)