BOJ 15732 - 도토리 숨기기

문제

백준 온라인 저지 - 15732번

풀이 과정

일정한 간격으로 도토리가 놓여있다고 했을 때 특정 순서의 도토리가 들어있는 상자의 위치를 찾는 문제입니다.

만약 주어진 규칙들을 모두 수행해보고 도토리의 위치를 찾는 브루트 포스 를 수행한다면
최악의 경우 O(NK) 이기 때문에 시간 초과가 발생합니다.

대신에 상한과 하한을 설정한 뒤 이분 탐색 을 활용해서 마지막 도토리가 있는 상자의 위치를 찾도록 하겠습니다.
각각의 위치에서 해당 지점이 마지막 도토리라는 사실을 어떻게 판단할 수 있을까요?
이는 바로 각 규칙을 모두 순회하면서 특정 지점 x 보다 앞에 있는 도토리의 개수를 세어주면 됩니다.
각 규칙의 시작 위치를 init , 간격을 step , 기준 지점을 x 라고 한다면 다음과 같은 부등식이 성립합니다.

init + step * a <= x

여기서 a 는 step 의 개수이며 a + 1 이 x 와 같거나 작은 원소의 개수가 됩니다.

코드

import sys


N, K, D = list(map(int, sys.stdin.readline().split()))
rules = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]


def dotori(pivot):
    total = 0
    for start, end, step in rules:
        beta = min(end, pivot)
        if start <= beta:
            calc = (beta - start) // step + 1
            total += calc

    return total


def solution():
    lo, hi = 1, 1000000

    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2

        if dotori(mid) >= D:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    return ans


print(solution())