그릇모으기

dp문제로 아직 실력이 부족하여 푸는데 무척 어려웠다.

다른사람의 코드를 힌트로 삼아 풀었다.

시도 1

DP(I,J) : I ~ J 뭉치를 하나의 뭉치로 합쳤을때 최소 횟수

DP(I,J) = MIN(DP(I,K)+DP(K+1,J)+두개를 합치는 횟수)

오류가 있다 전체 다를 고려해야 최솟값이 나온다 분할해서 합치면 최소 횟수가 나오지 않는다.

시도 2

정렬을 시키고 각 포지션을 DFS로 탐색하여 최솟값을 구한다.

지수의 복잡도를 가지므로 안된다.

해결방법

총 이동 횟수 = 분할된 조각 수 * 2 - n - 1 이된다.

최솟값을 구할려면 분할된 조각 수가 최소가 되는 것을 찾아야 한다.

dp[p][prev] : 위치가 p일때 이전 조각의 뭉치 번호가 prev 일때 최소 분할 조각 수라 하자

dp[p][prev] = min(dp[np][prev'] + p~np-1 까지 분할된 조각 수)

이때 p에 위치된 값과 같은 것이 여러개 주어 질 수 있다.

만약 판의크기가 1인 것이 뭉치 번호 1,2,3,4,5,6에 있다고 가정하면

뭉치 번호 1로 시작해서 2,3,4,5,6으로 끝나는 경우

뭉치 번호 2로 시작해서 1,3,4,5,6으로 끝나는 경우 ....

이렇게 경우의 수가 나눠지며 해당 경우에 대해서 모두 구해보면 최솟값을 구할 수 있다.

시작과 끝 번호만 중요하고 나머지는 전혀 중요하지 않다.

마지막은 다음 재귀를 위해서 처음은 이전 위치와 비교하여 분할 조각수를 계산할 수 있기 때문이다.

복잡도는 O(2500*50*2500)이 된다. 사실 시간초과가 날거라 예상했는데 통과하였다.

아마도 위치 P와 이중 루프간와 서로 관계가 있기 때문이라 생각한다.

루프의 길이가 크면 그만큼 P가 건너 뛰기 때문이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

int parr, dp[2500][51];

pair<int,int> arr[2500];

int solve(int p, int prevFrom){

if(p==parr) return 0;

int &ret = dp[p][prevFrom], np = p, cal;

if(ret != -1) return ret;

ret = 1000000;

while(++np < parr && arr[np].first == arr[p].first);

for(int i=p; i<np; i++){

for(int j=p; j<np; j++){

if(i==j && p!=np-1) continue;

int cal = np - p;

if(arr[i].second == prevFrom) cal--;

ret = min(ret, solve(np,arr[j].second) + cal);

}

}

return ret;

}

int main () {

freopen("sample.txt", "r", stdin);

setbuf(stdout, NULL);

int T;

scanf("%d", &T);

for(int tc = 1, n, h, val; tc <= T; tc++) {

parr = 0;

scanf("%d", &n);

for(int i = 0; i < n; i++){

scanf("%d", &h);

for(int j = 0, prevVal = 0; j < h; j++){

scanf("%d", &val);

if(val != prevVal){

arr[parr++] = make_pair(val,i);

prevVal = val;

}

}

}

sort(arr, arr + parr);

memset(dp,-1,sizeof(dp));

printf("#testcase%d\n%d\n", tc, 2*solve(0, 50)-n-1);

}

return 0;

}