[백준] 1072 게임

📌문제 링크

1072 게임

💡문제 풀이

1. 구해야 하는 것 : 몇 번의 게임을 더 해야 승률이 오르는지 (지는 경우는 없기 때문에 승률이 변하는 경우는 오르는 경우밖에 없다.)
2. 1번을 구하는데 필요한 기준 : 승률

형택이는 게임에서 지지 않으므로 이미 승률이 100인 경우에는 절대 변하지 않는다.
-> x==y일 경우 -1 출력하고 종료시킴
(이렇게 생각했는데? 틀렸습니다 ㅎㅎ z >= 99 일 때 -1 출력해야 함)

end 기준을 뭘로 정해야 하지...?
일단 x로 정했습니다
왜냐면 x만큼 더 하면 최대 50%까진 오를테니까..
(x = n, y = 0이라고 했을 때, (n / 2n) * 100 = 50)

---

승률을 계산할 때

1. z = int((y / x) * 100)
2. z = int(y * 100 / x)
3. z = y * 100 // x

처음에 1,2번 방법으로 해봤는데 이거 두 개가 결과가 다르더라고요???
50 29 이 테스트케이스로 해봤을 때 z가 58이 나와야 하는데 1번 방법으로 했을 때 57이 나옵니다
이유는 실수형에서 정확한 값을 저장하기 어려워서 부정확한 값이 나올 수 있기 때문이래요
1번에서는 실수 연산을 2번 해서 더 부정확한 값이 나오는 거라고 하네요

1. 정수 / 정수 = 실수, 실수 * 100 = 실수
2. 정수 * 100 = 정수, 정수 / 정수 = 실수
3. 정수 * 정수 // 정수 = 정수

그래서 모두 정수 연산을 하는 3번 방법이 가장 정확하다고 합니다

파이썬에서는 int의 범위가 거의 무제한이기 때문에 y * 100을 먼저 해줬는데
다른 언어일 경우 범위가 넘어갈 수 있으니 주의해야 할 것 같습니다

📋틀린 코드

1차 시도... 20% 언저리에서 틀렸다고 나옴

# 1072 게임
x, y = map(int, input().split())

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

# z = int((y / x) * 100)
z = int(y * 100 / x)


# 정민언니 팁대로 함수로 풀어봄
# 파이썬은 함수가 더 빠르다고 하네요... (걍 시스템적 문제)
def binary_search(start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = int(((y + mid) / (x + mid)) * 100)

        # 승률이 오르지 않는 경우 게임 수 올림
        if total <= z:  # 처음에 여기 등호 안넣었다가 계속 결과 1 나옴 ㅎㅎ
            start = mid + 1
        # 승률이 오른 경우 게임 수 낮춤
        else:
            result = mid
            end = mid - 1

    return result


print(binary_search(1, x))

처음에 위에서 설명한 2번 방법으로 승률을 계산했는데 부정확하게 나올 수 있다고 해서 3번으로 바꿨습니다
이거땜에 틀렸나..?

2차 시도

z = y * 100 // x

이렇게 바꿔도 20%에서 틀렸다고 뜸ㅋㅋ
이 문제가 아니었습니다........

📋맞은 코드

틀렸던 이유!!!
승률이 오르지 않는 경우는 승률이 100%일때만 있는 게 아니라 99%일 때도 오르지 않는다고 합니다...
그래서 고쳐줬더니 맞음!!

# 1072 게임
x, y = map(int, input().split())
z = y * 100 // x

# 승률이 99% 이상일 때 승률은 더 오르지 않음
if z >= 99:
    print("-1")
    exit()


# 정민언니 팁대로 함수로 풀어봄
# 파이썬은 함수가 더 빠르다고 하네요... (걍 시스템적 문제)
def binary_search(start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = (y + mid) * 100 // (x + mid)

        # 승률이 오르지 않는 경우 게임 수 올림
        if total <= z:  # 처음에 여기 등호 안넣었다가 계속 결과 1 나옴 ㅎㅎ
            start = mid + 1
        # 승률이 오른 경우 게임 수 낮춤
        else:
            result = mid
            end = mid - 1

    return result


print(binary_search(1, x))