BOJ 6101 - 식당

image.png

항상 정답은 NN이하이다. 모두 길이 11의 그룹으로 묶으면 되기 때문이다.

정답이 줄어드는 경우는 서로다른 kk개의 수를 가진 집합이라면 길이가 최소 k2k^2초과여야 한다.

이는 k2Nk^2 \le Nkk 가지의 경우만 각각 따지면 된다는 것을 의미한다.

Li,jL_{i,j}ii로 끝나는 서로 다른jj개의 숫자가 나오는 구간의 가장 왼쪽이라고 하자.

O(NN)O(N \sqrt{ N }) 에 투포인터로 전처리가 가능하다.

그럼 이제 $dp[i]=\text{Min}{j=1}^{\sqrt{ i }} dp[L{i,j}-1]+j^2$ 임을 알 수 있고 문제를 해결가능하다.

Tags:

Categories:

Updated:

Comments