먼저, 티셔츠의 안쪽 숫자와 바깥쪽 숫자를 간선으로 잇는다. 이제 그래프에서 각각의 간선에 대해 하나씩 정점을 중복 없이 할당해 주어야 하는 문제가 된다. 그렇게 얻어진 그래프의 각 컴포넌트를 생각해보자.
일단, 간선 개수 > 정점 개수 라면 중복 없이 할당하는게 불가능하다. 그러면 남는 경우의 수는 2가지인데,
간선 개수 = 정점 개수 - 1 인 트리 컴포넌트가 나오거나, 간선 개수 = 정점 개수인 사이클이 하나에 트리가 뻗어나오는 그래프가 있겠다. 여기서 관찰을 하나 할 수 있는데, 트리에서의 리프 노드, 즉 이어진 간선이 1개인 정점은 무조건 그 이어진 간선에 해당 정점을 할당해주는 식으로 컴포넌트의 크기를 줄여나갈 수 있다. 정점 개수와 간선 개수가 모두 1씩 감소하기에, 이렇게 해도 여전히 문제 해결이 가능한 컴포넌트가 남는다.
이 컴포넌트의 크기를 줄여나가는 과정은 위상정렬의 아이디어를 빌릴 것이다. 이어진 간선이 1개인 점들을 다 큐에 넣고, 하나하나 pop하면서 그 정점을 제거했을 때 새로 생기는 간선이 1개인 점들을 추가해 주자. 더 이상 큐에 값이 남지 않을 때까지 돌려주면, 트리 컴포넌트의 간선들에는 정점 할당이 끝날 것이고, 간선 개수 = 정점 개수인 컴포넌트에는 사이클 하나가 남을 것이다.
먼저 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를 삭제해야 할지 알 수 있다.
제자리가 아닌 사탕이 있으면, 결국 그 사탕을 원래 자리로 옮겨줘야 하고, 그 과정을 잘 나누고 이어서 진행하면 문제가 해결될 것이라고 생각해 볼 수 있다. 특히 사탕을 옮겨 놓게 되면 그 위치는 사탕의 개수가 K+1개이므로, 제자리가 아닌 사탕이 있어 항상 그 자리에서 유의미한 이동을 이어 나갈 수 있음을 확인할 수 있다. 제자리에 가져다 놓은 사탕은 더 이상 이동할 일이 없다는 것이다.
한 바퀴가 돌면, 제자리가 현재 위치보다 앞쪽인 사탕의 개수가 하나 줄어들게 되고, 유의미한 이동이 보장되어 바퀴의 수와 그 사탕의 개수가 같음이 보장되므로 그 개수만 세 주면 문제가 해결된다.
하지만 1번 자리는 위의 공식이 적용될 수 없어 무의미한 이동이 발생할 가능성이 있으며, 처음 주어진 상태에 1번 자리가 완성돼 있으면 이를 해소하기 위해 1을 옮기고 다시 가져오는 한번의 이동이 추가로 필요하다. 이를 체크해 주면 문제를 해결할 수 있다.