99클럽 코테 스터디 1일차 TIL + 이분탐색

[백준/파이썬] 1072 게임

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

 

import sys
input = sys.stdin.readline

x, y = map(int, input().split())
prevZ = y * 100 // x
result = 0

if prevZ >= 99:
    result = -1
else:
    start = 0
    end = x
    while start <= end:
        mid = (start+end) // 2
        z = (y+mid)*100 // (x+mid)
        if z > prevZ:
            result = mid
            end = mid - 1
        else:
            start = mid + 1

print(result)

 

• 몇 번의 게임을 더 하더라도 승률 99에서 100은 나올 수 없으므로 if문 조건을 나눔
• 처음엔 곱하기, 나누기 연산 순서 상관없이 * 100을 뒤에 해주어 값을 찾을 수 없었다 . 한 번 더 생각하기 !

 

• 이분탐색 조건
  • 오름차순으로 정렬되어 있어야 함
  • mid와 찾고자 하는 값(target)을 비교
  • target과 mid값에 따라 탐색 범위를 좁힘
    
    • target > mid : start = mid + 1
    • target < mid : end = mid -1
  • while start <= end 조건을 해당할 경우에 이분탐색을 실행할 수 있음
  • O(logN)