CuttingSticks/하기웅

이야기

다이내믹 프로그래밍에 대한 이론적이 이해는 있어도 구현에 있어서 어려움을 가지고 있었는데... 너무 지레 겁을 먹었던 것 같다~~ 시간이 느리긴 하지만 막상 짜놓고 보니 그렇게 어려운게 아니었던 것 같다.

소스

#include <iostream>
using namespace std;

struct Stick {
	int len;
	int cost;
};

Stick stick[51][51];

int stickLen, cuttingTime, cuttingPart, preCutting; 
int i,j,k,stickNum;

int calculate()
{
	stickNum=2;
	while(stickNum!=cuttingTime+2)
	{
		for(i=0,j=stickNum; i<cuttingTime-stickNum+2; i++,j++)
		{
			stick[i][j].cost=1000000;
			stick[i][j].len = stick[i][j-1].len+stick[i+1][j].len-stick[i+1][j-1].len;
			for(k=i+1; k<j; k++)
				if(stick[i][j].cost > stick[i][k].cost + stick[k][j].cost + stick[i][k].len + stick[k][j].len)
					stick[i][j].cost = stick[i][k].cost + stick[k][j].cost + stick[i][k].len + stick[k][j].len;
		}
		stickNum++;
	}
	return stick[0][cuttingTime+1].cost;
}

int main()
{
	while(cin>>stickLen)
	{
		if(stickLen==0)
			break;
		cin>>cuttingTime;
		preCutting=0;
		for(i=0; i<cuttingTime; i++)
		{
			cin >> cuttingPart;
			stick[i][i+1].len=cuttingPart-preCutting;
			stick[i][i+1].cost=0;
			preCutting = cuttingPart;
		}
		stick[cuttingTime][cuttingTime+1].len=stickLen-preCutting;
		stick[cuttingTime][cuttingTime+1].cost=0;
		cout << "The minimum cutting is "<<calculate()<<"."<<endl;
	}
	return 0;
}