15732번: 도토리 숨기기

Memo

로직 설명

• 모든 규칙에 대해서 배열에 누적해서 값을 저장하면 시간초과가 난다는 판단이 섰습니다.
• 상자의 위치를 기준으로 이분탐색을 돌립니다. mid값을 정했을때 숨길 수 있는 도토리 갯수를 구하여 이분탐색을 진행합니다.

Code

제출 날짜

2021/06/12

import sys

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

left = 1
right = 1000000

while (left <= right):
    mid = (left + right) // 2
    cnt = 0
    for i in range(K):
        start, end, interval = li[i]
        if (mid < start):
            continue
        elif (start <= mid and mid <= end):
            cnt += (mid - start) // interval + 1
        else:
            cnt += (end - start) // interval + 1
    if (cnt >= D):
        right = mid - 1
    else:
        left = mid + 1
print(left)