[백준(Baekjoon)] 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

입력	출력
10 8	1
100 80	6
47 47	-1
99000 0	1000
1000000000 470000000	19230770

---

나의 풀이

[Python(파이썬)]

 

풀이 1 - 시간 초과

total, win = map(int, input().split())
percent, time, temp = int(win / total * 100), 0, 0

if total == win:
    print(-1)
else:
    for i in range(1, 1000000000):
        temp = int((win+i) / (total+i) * 100)
        time += 1
        if percent != temp:
            print(time)
            break

 

풀이 2 - 이진 탐색 풀이 (다른 사람 풀이 참조)

total, win = map(int, input().split())
percent = win * 100 // total
first, last = 1, total

if percent >= 99:
    print(-1)
else:
    while first <= last:
        mid = (first + last) // 2
        if (win+mid) * 100 // (total+mid) <= percent:
            first = mid + 1
        else:
            answer = mid
            last = mid - 1
    print(answer)

 

---

풀이 과정

이 문제는 시간 초과가 안 나오게 하는 것이 관건인 문제인 것 같다. 

 

처음에는 이진탐색을 생각하지 않고 그냥 한개씩 더해가면서 풀었더니 시간초과가 나왔다. 

1 ≤ X ≤ 1,000,000,000 범위가 너무 커서 숫자가 커질 수록 시간이 많이 드는 것이었다. 

 

그래서 방법을 찾아보다 이 문제는 이진탐색(이분 탐색) 알고리즘을 통해 풀어야하는 것을 알았다. 

이진 탐색 알고리즘을 통해 처음 문제를 풀다보니 어려움을 겪고 다른 사람들의 풀이를 보면서 학습하며 풀었다. 

 

[Algorithm] 이진 탐색(Binary Search, 이분 탐색, 이진 검색)

 

 

문제를 풀면서 발생한 또 한가지 문제는 승률 구하는 방법에서 생겼다. 

 

승률을 구하는 방법에는 두가지 방법이 있다. 

1. int(win / total * 100) 

2. win * 100 // total

 

이 문제에서는 1번째 방법  int(win / total * 100) 을 사용해서 구현하니 틀렸다고 나왔다. 

 

>>> 58 / 100
0.58

>>> 58/100*100
57.99999999999999

>>> int(58/100*100)
57

>>> 29 / 50
0.58

>>> 29 / 50 * 100
57.99999999999999

 

위와 같이 58 / 100 한다음 100을 곱해주면 58이 나와야하는데 57이 나오는 것이다. 

 

글 읽기 - 29/50=0.58과 29/50*100=57.9999999 (acmicpc.net)

글 읽기 - 29/50=0.58과 29/50*100=57.9999999

 

파이썬에서 실수 자료형은 정확한 수를 담지 않는다고 한다. 따라서 위 문제를 해결하기위해 

 2번 win * 100 // total 로 승률을 구해야한다. 

 

 

---

문제 출처

1072번: 게임