BOJ 6101 - 식당
항상 정답은 $N$이하이다. 모두 길이 $1$의 그룹으로 묶으면 되기 때문이다.
정답이 줄어드는 경우는 서로다른 $k$개의 수를 가진 집합이라면 길이가 최소 $k^2$초과여야 한다.
이는 $k^2 \le N$ 인 $k$ 가지의 경우만 각각 따지면 된다는 것을 의미한다.
$L_{i,j}$ 를 $i$로 끝나는 서로 다른$j$개의 숫자가 나오는 구간의 가장 왼쪽이라고 하자.
$O(N \sqrt{ N })$ 에 투포인터로 전처리가 가능하다.
그럼 이제 $dp[i]=\text{Min}{j=1}^{\sqrt{ i }} dp[L{i,j}-1]+j^2$ 임을 알 수 있고 문제를 해결가능하다.
Comments