[백준] 1072 게임 / python

문제

https://www.acmicpc.net/problem/1072

1072번: 게임

 

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

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

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

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

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

입력

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

출력

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

 

코드

import sys
input = sys.stdin.readline

x,y = map(int, input().split())
z = (y*100)//x

if z >= 99:
    print(-1)
else:
    answer = 0
    left = 0
    right = x

    while left <= right:
        mid = (left+right) // 2
        if (y+mid)*100 // (x+mid) <= z:
            left = mid+1
        else:
            answer = mid
            right = mid-1
    print(answer)

 

Z가 99 이상이라면 승률은 절대 변하지 않으므로 -1을 출력한다.

나는 처음에 순차적으로 탐색하는 방법으로 코드를 구현했는데 생각해보면 X는 최대 1,000,000,000까지 가능하므로 순차적으로 탐색하는 O(n)의 시간복잡도를 적용하면 시간초과가 날 수 밖에 없다.

 

1부터 X까지 오름차순인 상태에서 탐색 가능한 이진 탐색을 구현했다.

 

NEW

이진탐색(Binary Search)

데이터의 크기가 매우 클 때 선형 탐색 대신 쓸 수 있는 방법이 이진 탐색이다.

N개의 데이터가 있을 때 범위를 절반씩 줄여나가므로 O(logn)의 효율적인 시간복잡도를 가진다.

주의할 점은 정렬된 상태여야한다.

리스트의 전체 범위에서 시작해야 하므로 left, right 두 개의 변수가 필요하다.

보통 left는 시작을 뜻하는 0, right는 끝을 뜻하는 len(data)-1로 선언

left <= right인 동안 반복을 계속 돌려주면 된다.

 

 

int((Y/X) * 100)로 구현했는데 틀렸습니다 가 나왔다.

int((Y*100)/X) 나 (Y*100)//X는 정답으로 처리됐다.구글링해보니 python에서는 부동소수점 오차가 나서 정확하지 않다고 한다.