[백준/python]15732번 도토리 숨기기 - binary search

1300번 문제 K번째 수와 유사한 문제이다. 어떤 것을 기준으로 이분 탐색을 할 지 찾는 것이 중요하다.

# 도토리 숨기기 (binary search) 1300번문제와 유사
import sys
def input():
    return sys.stdin.readline()

N,K,D = map(int, input().split())
rule=[]
for i in range(K):
        line = list(map(int, input().split()))
        rule.append(line)

ans=0
s,t=0, N+1
while t-s>1:
    
    mid = (s+t)//2
    
    tmp=0
    for i in range(K):
        r = rule[i]
        A,B,C = r[0], r[1], r[2]
        
        if mid < A  : 
            continue
        
        if mid > B :
            dtr = ( (B-A)//C) +1
            
        else:
            dtr = ( ( mid-A )//C ) +1
        tmp+=dtr
    

        
    if tmp >= D:
        ans = mid
        s,t=s,mid
    
    elif tmp < D:
        s,t = mid,t
        
print(ans)

마지막 상자의 번호를 기준으로 이분 탐색을 실행한다. 만약 X번 상자가 마지막 상자일 때 도토리의 개수가 주어진 D보다 크다면 마지막 상자의 번호를 더 낮은 곳에서 탐색한다. 이 때 mid 값을 답으로 저장해둔다.

이분 탐색 내에서 mid가 주어진 규칙에서 주어진 범위의 상자보다 큰 번호인 경우와 주어진 범위 내에 있는 경우 도토리를 다르게 세어 주어야 한다.