imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:03Z

New page

== 소감 ==
{| class="wikitable"
|-
| 2005-12-28 Accepted 0.785 452
|}
== 코드 ==
// 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]] [[문보창]]

CuttingSticks/문보창 - Revision history

imported>Unknown at 05:23, 7 February 2021