99클럽 코테 스터디 1일차 TIL - [이진탐색]

오늘의 문제

 

 

---

정답 코드

x,y = map(int,input().split())
z = y*100//x
result = -1
l = 0
r = 1000000000

while l <= r :
    mid = (l+r)//2
    temp = (y+mid)*100//(x+mid)
    if temp != z :
        result = mid
        r = mid-1
    else :
        l = mid+1

print(result)

---

오늘의 회고

 

뻘짓... 이진탐색 문제를 처음 풀어봐서 너무 어려웠다. 

우선 알고리즘의 원리에 대해서 파악하고 나서 이걸 문제에 어떻게 적용하는지 풀이 방법을 찾았다.

 

문제 해설 :

Start point = 0, End point = 10억 으로 설정하고 이분탐색 코드로 mid 값을 찾는다.

이 mid 값은 총 진행하는 추가적인 게임의 수라고 생각한다.

(경우 1) mid 번의 게임을 진행했을 때의 승률을 구해서 현재 승률인 z와 같다면, 승률이 변하기 위해서는 더 많은 게임을 해야 하는 것이므로 mid를 기준으로 오른쪽으로 넘어가서 탐색한다. 끝까지 탐색을 했음에도 계속해서 승률이 같은 경우에는 -1 을 출력해야 하므로, result 값은 갱신되지 않는다. 왼쪽 탐색으로 넘어가게 된다면, 그 때 갱신을 하게 될 것이다.

(경우 2) mid 번의 게임을 진행했을 때의 승률이 현재 승률인 z와 다르다면, mid를 기준으로 왼쪽으로 넘어가서 탐색하면서, 몇 번의 게임을 진행할 때 최소 게임 횟수가 되는지 찾을 때까지 계속 탐색을 진행한다. result 값을 계속 갱신해주며 마지막 갱신이 될 때까지 반복한다.

마지막 갱신된 값이 정답!