빼빼로 포장

$F_i=(B_i,U_i)$를 앞 $i$개의 빼빼로로 만들 수 있는 최적 상태라 하자. $B_i$는 상자 수이고 $U_i$는 사용량이다. 비교할 때 $B_i$가 큰 상태, 같다면 $U_i$가 작은 상태를 고른다. $i$번 빼빼로를 쓰지 않으면 $F_{i-1}$을 유지한다. 마지막 상자가 $(k+1)$번부터 $i$번까지라면 누적 합 $Q_i-Q_k\geq X$이고 후보는 $(B_k+1,U_k+i-k)$이다. 마지막 상자를 고정하면 앞부분도 최적이어야 하므로 이 점화식은 모든 해를 빠짐없이 고려한다. 첫 서브태스크는 모든 $k$를 확인하여 $O(N^2)$에 해결한다. 전체 풀이에서는 양의 무게 때문에 $Q_i$가 증가한다는 사실을 쓴다. $Q_k\leq Q_i-X$인 인덱스가 차례로 후보에 들어오므로 포인터로 각각 한 번만 추가한다. 후보 중 $B_k$가 최대이고 그중 $U_k-k$가 최소인 상태 하나만 유지하면 된다. 각 $i$에서 그 상태와 $F_{i-1}$을 비교한다. 시간 $O(N)$, 공간 $O(N)$이다.

Solution written by GPT6.1