[Python] 1072. 게임

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

1072번: 게임

 

접근법

• 승률은 (Y * 100) // X로 구함. → 부동소수점 연산 때문
• 승률이 99이상일 경우 -1 출력 → 99%인 경우는 이미 한번 졌기 때문에 절대 100%가 될 수 없음.
• 들어올 수 있는 값이 매우 크기 때문에 재귀가 아닌 이분 탐색을 활용

def count_play(X, Y):
    Z = (Y * 100) // X
    # X = (Y/Z) * 100으로 작성하면 부동소수점 때문에 틀림.
    if Z >= 99: # Z가 99이상이라면 승률은 절대 변하지 않음. 한번이라도 이미 졌기 때문에 절대 100이 될 수 없음.
        print("-1")
        return 
    answer = 0
    left = 1 # 시작 인덱스
    right = X # 끝을 나타냄

    while left <= right:
        mid = (left + right) // 2
        # 현재의 승률이 처음 승률보다 작을 경우, 이긴 횟수를 줄여야 함.
        if Z < ((Y+mid)*100 // (X + mid)):
            answer = mid
            right = mid - 1
        # 현재의 승률이 처음 승률보다 크거나 같을 경우, 이긴 횟수 증가해야함.
        else:
            left = mid + 1
    print(answer)

def main():
    X, Y = map(int, input().split())
    count_play(X, Y)

 

---

유의할 점 및 새로 배운 사항 

 

1. 파이썬의 실수 연산

1. ( X * 100) // Y

2. (X // Y) * 100

1과 2의 연산은 실수의 연산으로 그 값이 같지 않을 수 있다.

그 예론 X = 29, Y = 50이 있다.

정수에서 연산 후 조금의 오차라도 발생한다면 int형으로 버림될 수 있기 때문.

따라서 실수의 연산은 부정확할 수 있으므로 주의해야한다.

참고 링크 : [백준] 1072 : 게임 파이썬 리뷰 - 연산 오류

 

2. 이분 탐색 시 범위 줄이기

mid번 이겼을 때와 처음의 승률을 비교하여 이분 탐색의 범위를 조정해야한다.(처음의 승률보다 1큰 승률을 찾아야 하기 때문에)

(1) 만약 mid번 이겼을 때의 승률이 처음 승률보다 크다면, 이분 탐색의 범위를 줄여야 한다. 

-> right를 mid -1 로 이동시킴

(2) 만약 mid번 이겼을 때의 승률이 처음 승률보다 작다면, 이분 탐색의 범위를 늘려야 한다.

-> left를 mid + 1로 이동 시킴 

---

처음 생각했던 알고리즘의 문제점(틀린이유)

try 1
ans 라는 변수를 두고, 재귀적으로 함수를 호출하면서 새로 구한 win_rate와 기존 win_rate가  비교
win_rate가 100혹은 99이면 승률이 절대 변하지 않기 때문에 -1 출력하도록 함. 

• 재귀의 maximum 횟수가 정해져있고, 이를 초과하는 답이 나오는 경우 에러가 나옴.
  → 이를 피하기 위해 sys.setrecursionlimit을 사용했지만, 사용한 max 횟수를 넘기는 경우가 존재하기 때문에 재귀를 사용하지 않은 방법을 찾아야 함.

import math
import sys
sys.setrecursionlimit(10000)
def count_play(X, Y, win_rate, count):
    updated_win_rate = math.trunc((Y / X) * 100)
    if (win_rate == 100) or (win_rate == 99):
        print("-1")
        return count

    if updated_win_rate == win_rate:
        count += 1
        count_play(X + 1, Y + 1, win_rate, count)
    else:
        print(count)
        """
        여기서 print하는 것이 아니라 main에서 출력하려고 하면 어떻게 해야할까?
        재귀때문에 count가 바뀐다. 
        재귀로 호출하는 것 때문에 일부러 count_play(..,count +1) 로 호출하는 것이 안리ㅏ
        count += 1을 수행한 후 재귀를 호출했는데, 왜 숫자가 주는지 모르겠음.
        -> count_play()를 재귀호출 할 때 return을 활용해주면 됨.
        """
        return

def main():
    X, Y = map(int, input().split())
    ans = 1
    win_rate = math.trunc((Y / X) * 100)
    count_play(X + 1, Y + 1, win_rate, ans)

if __name__ == "__main__":
    main()

사용된 알고리즘

수학, 이분탐색