== 소감 ==
|| 2005-12-28   Accepted   0.785   452 ||
== 코드 ==
{{{~cpp
// 10003 - Cutting Sticks
#include <iostream>
using namespace std;
//#include <fstream>

#define MAX_CUT 53
#define MAX_NUM 0x7fffffff

//fstream fin("in.txt");

static int lenStick, numCut;
static int cut[MAX_CUT];
static int d[MAX_CUT][MAX_CUT];

bool input()
{
	cin >> lenStick;
	if (lenStick == 0)
		return false;
	cin >> numCut;
	for (int i = 1; i <= numCut; i++)
		cin >> cut[i];
	return true;
}

void initTable()
{
	cut[0] = 0, cut[numCut+1] = lenStick;
	for (int i = 0; i <= numCut; i++)
		d[i][i+1] = cut[i+1] - cut[i];
}

int process()
{
	initTable();

	int j, min;
	for (int step = 1; step <= numCut; step++)
	{
		for (int i = 0; i <= numCut - step; i++)
		{
			j = i + step + 1;
			min = MAX_NUM;
			for (int k = i + 1; k <= j - 1; k++)
			{
				if (min > d[i][k] + d[k][j])
					min = d[i][k] + d[k][j];
			}
			d[i][j] = min + cut[j] - cut[i];
		}
	}
	return d[0][numCut+1] - lenStick;
}

inline
void show(const int result)
{
	cout << "The minimum cutting is " << result << ".\n";
}

int main()
{
	int result;
	while (input())	
	{
		result = process();
		show(result);
	}
	return 0;
}
}}}
----
[CuttingSticks] [문보창]