[BOJ] Python 백준 1072번 게임 실버 3

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

1072번: 게임

전형적으로 이진 탐색을 사용하는 문제이다.

혹시 이진 탐색을 처음 접하거나 익숙하지 않다면 관련 포스팅을 보고 이해한 뒤 문제를 푸는게 좋을 것 같다.

 

2021.12.02 - [알고리즘/알고리즘 강의] - (알고리즘) 이진탐색 / 이분탐색 (Binary Search)

(알고리즘) 이진탐색 / 이분탐색 (Binary Search)

 

문제 풀이

---

문제에서 전체 게임 횟수 : X, 이긴 게임 횟수 : Y, 승률 : Z이다.

주의해야 할 조건은 3가지다.

 

1. 승률을 뜻하는 Z는 소수점을 버린다.(반올림이 아니다)
2. Z가 절대 변하지 않으면 -1을 출력한다.
3. X는 최대 1,000,000,000 (10억)까지 가능하다.

Z에 대한 식을 나타내 보면 Z=(Y*100)/X이고 a만큼 수행했을 때 Z+1=((Y+a)*100)/(X+a)가 성립하는 최소 a를 구하는 문제이다. (승률 = 이긴 횟수/전체 횟수)

참고로 Python의 계산 방식 때문인지 처음에 Z=(Y//X)*100로 작성했더니 틀렸었다.

꼭 Z=(Y*100)//X로 작성해야하고 이 부분에 대해서 정확히 아시는 분이 계시다면 피드백 해주시면 감사합니다!!

이때 Z가 99 이상이라면 승률은 절대 변하지 않으므로 -1을 출력하고 98일 때 생각하면 X번만큼 추가할 때 99로 변하기 때문에 최대 X번까지만 반복하면 된다는 것을 알 수 있다.

이때 X는 최대 10억까지 가능하므로 순차적으로 탐색하는 O(n)의 시간 복잡도를 적용한다면 반드시 시간 초과가 날 수밖에 없다.

즉 1부터 X까지 오름차순인 상태에서 탐색 가능한 이분 탐색(이진 탐색)을 적용하면 풀 수 있을 것이다.

다음은 전체 코드다.

 

x,y=map(int,input().split()) 
z=(100*y)//x 
left=0 
right=x 
res=x 
if z>=99: 
    print(-1)
else: 
    while left<=right: 
        mid=(left+right)//2 
        if (100*(y+mid))//(x+mid)>z: 
            res=mid 
            right=mid-1 
        else: 
            left=mid+1
    print(res)

res는 정답인 최소 게임 수를 의미하는 변수로 최대 X번을 저장해놓고 더 작은 수가 있으면 갱신하는 방식으로 구현하였다.

승률이 99 이상이면 바로 -1을 출력하고 98 이하라면 이진 탐색을 실행한다.

초기 left는 0, right는 X로 설정하고 left와 right가 역전되지 않을 때까지 반복한다.

이때 left와 right 중간값을 기준으로 승률(Z)이 변하면 res를 갱신한 뒤 right는 중간값-1로, 변하지 않으면 left를 중간값+1로 변경함으로써 탐색해야 되는 범위를 절반씩 줄여준다.

즉 탐색 범위가 N이라면 범위를 절반씩 줄이므로 O(logn)의 시간 복잡도를 갖고, 10억의 Input이 들어와도 충분히 연산 가능해진다.

 

결과 화면

※조건을 잘 보고 Input의 크기에 따라 적절한 알고리즘을 적용하는 것이 중요한 것 같다.※