백준 도토리 숨기기(15732)

도토리 숨기기

1. 힌트

1)

2)

3)

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

2) 단순한 방법에서 시작할 수 있을까?

3) 내가 문제를 푸는 과정을 수식화할 수 있을까?

4) 문제를 단순화할 수 없을까?

5) 그림으로 그려볼 수 있을까?

6) 수식으로 표현할 수 있을까?

7) 문제를 분해할 수 있을까?

8) 뒤에서부터 생각해서 문제를 풀 수 있을까?

9) 순서를 강제할 수 있을까?

10) 특정 형태의 답만을 고려할 수 있을까?

3. 구현

import sys
input = sys.stdin.readline
N, K, D = map(int, input().split())
S = [list(map(int, input().rstrip().split())) for i in range(K)]

# x번상자까지만 담으면 D개 이상 담을 수 있는지 여부
def f(x):
	sum = 0
	for A, B, C in S:
		B = min(B, x)
		if A > B : continue
		sum += ((B - A) // C + 1)
		if sum >= D : return True
	return False
	
lo = 0; hi = N
while lo + 1 < hi:
	mid = (lo + hi) // 2
	if mid != 0 and f(mid) : hi = mid
	else : lo = mid
print(hi)

1) 시간 복잡도

2) 테스트 케이스