[백준 15732 파이썬] 도토리 숨기기 (골드2, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 없이 스스로 풀었나요? : ❌

---

백준 15732번 도토리 숨기기

솔루션

1. mid를 마지막 도토리가 담긴 상자의 번호라고 가정

2. mid까지 총 몇개의 도토리가 담겼는지 파악한다.

3. mid까지 담긴 도토리의 개수가 총 도토리 개수(d)보다 작으면, 해당 상자보다 뒤에 있는 상자에 마지막 도토리가 담겨있으므로 5.으로 간다.

4. mid까지 담긴 도토리의 개수 총 도토리 개수보다 크거나 같으면, 해당 상자가 마지막 도토리가 담겨있을 가능성이 있으므로 answer를 갱신하고 6.로 간다.

5. left = mid + 1로 범위를 조정하고 다시 1.로 돌아간다.

6. right = mid - 1로 범위를 조정하고 다시 1.로 돌아간다.

위 과정을 left > right일 때까지 탐색하면 마지막 도토리가 담긴 상자를 구할 수 있다.

소스 코드

import sys

input = sys.stdin.readline


def cnt_acorn(value):
    cnt = 0
    for start, end, step, in rules:
        end = min(value, end)
        if start <= min(value, end):
            calc_value = (end - start) // step + 1
            cnt += calc_value

    return cnt


if __name__ == "__main__":
    n, k, d = map(int, input().split())
    rules = [list(map(int, input().split())) for _ in range(k)]

    lt, rt = 1, n
    res = 0
    while lt <= rt:
        mid = (lt + rt) // 2
        if cnt_acorn(mid) < d:
            lt = mid + 1
        else:
            res = mid
            rt = mid - 1

    print(res)

---

후기

완전탐색으로 풀거나 딕셔너리를 사용해 풀어봤으나 시간초과에 걸렸다.
이분 탐색을 떠올리지 못해서 어려웠다.