백준 6101 식당

https://www.acmicpc.net/problem/6101

6101번: 식당

먼저 DP를 하는데, DP[i]를 i번째까지를 적절히 그룹을 나눠서 얻을 수 있는 비용의 최소값이라고 가정하자. 

 

그러면 DP[i]를 업데이트 할 때, j~i까지 음식의 종류가 k가지일 때 이것들을 하나의 그룹으로 만들어 DP[i]와 DP[j-1] + k^2 의 최소값으로 업데이트하면 된다. 그리고 이 k가 √n을 넘을 경우, 하나씩 그룹으로 나누는 것보다 손해이므로, O(n√n)짜리 풀이를 생각해 볼 수 있다.

 

그러면, 이 각각의 k에 대해,  j~i까지 음식의 종류가 k가지가 되는 최소의 j를 잘 업데이트하면 된다. (DP는 단조증가)

 

i-1에서 아래와 같이 K=1,2,3 인 경우의 집합이 나타난다고 생각해 보자. 

(3), (2, 3), (1, 2, 3) 

그러면 arr[i]=1이라고 생각해 보면, i에서는 위에서의 각각의 J에 대해 집합이 

(1,3), (1,2,3), (1,2,3)이 되고, 2번째 집합인 (1,2,3)은 지우면 K=2,3 에 대해 나머지 j는 그대로 가져갈 수 있다.

k가 1인 경우는 (1)과 i를 추가하면 된다. 이부분도 빈 집합을 앞에 추가하면 각 집합에 1을 추가한 뒤 하나의 집합을 삭제하는 원래의 방식으로 처리할 수 있다. 

 

처음에는 이걸 관리하기 위해 집합 자체를 관리하는 Bitset을 써야 된다고 생각했고, 그걸로 AC를 받긴 했다. bitset을 선언하는 등의 시간 상수가 생각보다 작은 모양. 하지만 역시 찜찜해서, 더 생각해본 결과 필요 없다는 걸 깨달았다. 

 

집합에 arr[i]가 포함되기 직전인 시점, 즉 지워지는 시점이 arr[j-1] = arr[i]가 되는 시점과 같기 때문에, 이를 체크하면 집합을 굳이 저장할 필요 없이 어떤 j를 삭제해야 할지 알 수 있다. 

 

필자는 List를 관리했는데, 그냥 배열 관리해도 문제가 없을거 같다.