백준 15732 도토리 숨기기

• 문제 링크: 15732 도토리 숨기기

문제

관찰
완전 탐색:
조건에 맞게 모든 상자에 다 넣어 준다.
1,000,000(상자수) * 10,000(조건수) 시간 복잡도로 TLE
시간을 줄이기 위해선 상자수 or 조건 수를 줄여줘야한다.
=> 파라메트릭스 서치로 상자 범위를 정하고
문제 조건에 해당 상자 범위가 해당하는 지 안하는 지 판단.

최대 10개의 상자가 있고 6 개의 도토리가 있으며 1개 상자마다 1개의 도토리가 있을 수 있다 할 때 파라메트릭스 서치를 계속 진행하면
6번째 상자에 도토리가 있음을 알수 있다.
s = 1, e = 10, mid = (10+1)//2
1턴
1 2 3 4 5 6 7 8 9 10
x 상자 5개는 도토리 6개를 못담는다.즉 조건 만족 안한다.
s mid e 조건에 만족하지 않기에 5 이하의 수는 모두 조건에 만족하지 않음으로 고려할 필요없다. 그래서 s = mid + 1 해준다.
2턴
1 2 3 4 5 6 7 8 9 10
x x x x x o 상자 8개는 도토리를 모두 담을 수 있다. 즉 조건 만족.
s mid e 8개 이상의 상자는 모두 조건 만족함으로 고려할 필요 없다.
그러므로 e = mid - 1
3턴
1 2 3 4 5 6 7 8 9 10
x x x x x o o o o 상자 6개는 도토리를 모두 담을 수 있다. 즉 조건 만족.
s e 6개 이상의 상자는 모두 조건 만족함으로 고려할 필요 없다.
mid
그러므로 e = mid - 1
기존 s <= e (1 <= 10) 에서 s > e (6 > 5) 가 된다. 이 때 파라메트릭스 서치를 종료하고 마지막으로 진행한 서치의 값이 최소 값이된다!
최종 결과
1 2 3 4 5 6 7 8 9 10
x x x x x o o o o o
시간 복잡도는 log (상자의수)

# 이분 탐색으로 정한 상자의 개수가 문제의 조건에 맞는 지 판단. 
def box(mid):
   dotori = 0
   for i in range(K):
       A, B, C = ABC[i][0],ABC[i][1], ABC[i][2]
       if A <= mid < B:
           dotori += (mid - A) // C + 1
       elif B <= mid:
           dotori += (B - A) // C + 1
   if dotori >= D:
       return True
   else:
       return False

# 이분탐색
def check():
   s, e = 1, 10**9
   ans = 0
   while s <= e:
       mid = (s+e)//2
       # 조건에 맞으면 정답 후보 (ans)에 저장하고 e 를 줄인다
       if box(mid):
           e = mid - 1
           ans = mid
       else:
           s = mid + 1
   return ans


N, K, D = map(int, input().split())
ABC = []
for _ in range(K):
   ABC.append((list(map(int, input().split()))))
print(check())

걸린 시간: 20분
ps 가 잘되니 좋다.