Memo
로직 설명
•
모든 규칙에 대해서 배열에 누적해서 값을 저장하면 시간초과가 난다는 판단이 섰습니다.
•
상자의 위치를 기준으로 이분탐색을 돌립니다. mid값을 정했을때 숨길 수 있는 도토리 갯수를 구하여 이분탐색을 진행합니다.
Code
제출 날짜
@6/12/2021
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)
Python
복사
