99클럽 코테 스터디 1일차 TIL - 이분탐색 (백준 1072번 )

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

 

• 오늘의 학습 키워드 : 이분탐색
• 공부한 내용

import sys

#게임 횟수 X, 승리 횟수 Y
X,Y = map(int,sys.stdin.readline().strip().split())

#재귀형 이진 탐색 함수 정의
def binary_search(X,Y,start,end):
    #1.종료-> start가 최소 게임 횟수 나타냄.
    if start>end:
        return start
    
    #중간값 
    mid = (start+end)//2
    # print("mid : ",mid)
    
    #mid 계산 후 승률 다시 계산(NEW Z)
    result = (Y+mid)*100//(X+mid)
    
    #2.새로 계산한 승률이 현재 승률보다 높은 경우
    if result>(Y*100//X):
        #더 적은 게임으로도 가능한지 확인-> 왼쪽으로 확장
        return binary_search(X,Y,start,mid-1)
        
    #3. 새로 계산한 승률이 현재 승률와 동일한 경우 
    elif result==(Y*100//X):
        #더 많은 게임이 필요하므로, 범위를 오른쪽으로 확장 
        return binary_search(X,Y,mid+1,end)

#승률이 이미 99프로가 넘어선 경우, 승률이 더이상 올라갈 수 없으므로 -1 출력
if Y*100//X>=99:
    print(-1)
else:
    #최소 추가 게임수:1, 최대 추가게임수 : 1000000000을 이용하여서 구하기
    print(binary_search(X,Y,1,1000000000))

# 해당 코드를 좀더 다듬어보기
import sys

X, Y = map(int, sys.stdin.readline().strip().split())
Z = (Y * 100 // X);
# 만약 승률이 이미 99% 이상이면 더 이상 승률을 올릴 수 없으므로 -1 출력
if Z >= 99:
    print(-1)
else:
    start, end = 1, 1000000000
    result = -1

    # start>end인 경우 그만두기
    # 이진 탐색 시작
    while start <= end:
        mid = (start + end) // 2
        new_Z = (Y + mid) * 100 // (X + mid)

        # 새로운 승률이 현재 승률보다 높다면
        if new_Z > Z:
            result = mid
            end = mid - 1  # 더 적은 게임수로 가능한지 확인
        else:
            start = mid + 1  # 승률이 변하지 않으면 더 많은 게임 필요
        # print(start,end,new_Z)

    print(result)

 

• 오늘의 회고
  • 사실 제일 처음 생각한건 제일 만만한건 for문으로 하나하나 해볼까 했다. 
    하지만 예제5번을 보면 for문을 사용하게 될 경우, 무조건 시간 초과가 날 수 밖에 없었다.. 그래서 이분탐색을 이용하고자 했다. 
    하지만, 두번째 문제는 너무우우우 오랜만에 문제를 푸니깐,, 이분탐색이 머였는지조차도 가물가물한 상태라는것..
    그렇기에.. 블로그에 쓴 내가 정리한 이분탐색 내용을 봤다🥲🥲
  • 그걸 보면서.. 생각한 방법은 이거였다
    1. 예시로 들면서. 만약에 start =1 , end = 10,000이라고 생각하고 그럴때 mid =5000이 나올 경우
    (Y+5000)*100 //(X+5000) > (Y*1000)//X 이 경우에는 더 줄일 수 있는 것이다. -> 이건 재귀함수를 더 불러야한다..
    ===> end = mid -1 대입
    2. 그럼 언제 그만두는가,,? if start > end 인 경우에는 start가 최대로 줄여진값이므로, 이 값을 최종 결과로 출력
    3. (Y+5000)*100 //(X+5000) == (Y*1000)//X 같은 경우에는..? 이건 Z 값이 달라지지 않았으므로, 재귀함수를 더 불러와야한다... ====> start = mid +1
• 오늘의 오랜만에 이분탐색을 풀어서.. 이분탐색을 다시 정리해보는 시간이 아니었을까,,? 이기회에 내가 잊어버리고 살았던~ 알고리즘 정리도 하고 아자아자 화이팅 👊