백준 6101 식당

https://www.acmicpc.net/problem/6101 6101번: 식당 [1] [2] [3] [4] [5, 6] [7, 8, 9, 10, 11] [12] [13] 과 같이 묶으면, 1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11의 비용이 든다. www.acmicpc.net 먼저 DP를 하는데, DP[i]를 i번째까지를 적절히 그룹을 나눠서 얻을 수 있는 비용의 최소값이라고 가정하자. 그러면 DP[i]를 업데이트 할 때, j~i까지 음식의 종류가 k가지일 때 이것들을 하나의 그룹으로 만들어 DP[i]와 DP[j-1] + k^2 의 최소값으로 업데이트하면 된다. 그리고 이 k가 √n을 넘을 경우, 하나씩 그룹으로 나누는 것보다 손해이므로, O(n√n)짜리 풀이를 생각해 볼 수 있다..

원문링크 : 백준 6101 식당