[Python/파이썬] 백준 15732번: 도토리 숨기기

문제

 

풀이

입력이 다음과 같을 때,

200 2 5
100 150 10
110 150 15

 

상자의 번호는 0 ~ 200까지 있다.

우선 중간 값(100)을 구하고, 0번 상자에서 100번 상자까지의 도토리 개수를 구한다.

도토리 개수에 따라 이분 탐색을 수행하면 된다.

코드

import sys
input = sys.stdin.readline

#도토리 수 구하기
def calAcorn(rules, boxNum):
    cnt = 0
    for start, end, margin in rules:
        if boxNum < start:
            continue
        end = min(boxNum, end)
        cnt += (end - start) // margin + 1
    return cnt 

def binarySearch(rules, end, find):
    start = 0
    while start < end:
        mid = (start + end) // 2
        midAcorn = calAcorn(rules, mid)
        if midAcorn < find:
            start = mid + 1
        else:
            end = mid
    return start

n, k, d = map(int, input().split())
rules = []
for _ in range(k):
    a, b, c = map(int, input().split())
    rules.append((a, b, c))

print(binarySearch(rules, n, d))

 

마무리

골드 2 수준의 알고리즘은 아닌 것 같다.