[BOJ] 15732. 도토리 숨기기

문제

---

골드 2

이분 탐색을 사용하면 쉽게 풀 수 있다.

포인트

---

규칙을 통해 도토리의 개수를 맞춰 상자의 개수를 특정하는 것 보다 먼저 상자의 개수를 특정하고 도토리의 수를 계산해 맞춰야한다. 즉 이분 탐색을 사용할 수 있다.

각 규칙에서의 도토리 개수는 시작부터 현재 상자의 차이를 간격으로 나눠 + 1 하면 알 수 있다.

코드

---

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

left = 0
right = n
result = 0
while left <= right:
    mid = (left + right) >> 1

    total = 0
    for i in range(k):
        if mid < rules[i][0]:
            continue
        elif mid >= rules[i][1]:
            dif = rules[i][1] - rules[i][0]
        else:
            dif = mid - rules[i][0]
        total += dif//rules[i][2] + 1

    if total < d:
        left = mid + 1
    else:
        result = mid
        right = mid - 1

print(result)