[문제] 막대기 자르기

막대기자르기.zip

0.00MB

 

[ 솔루션 ]

 

 

[ 참고 소스 코드 ]

#include <iostream>
using namespace std;

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w",stdout);
	
	int d[52][52]= {0, };
	int cut[52];
	int len, n, i, j, k;
	
	cin >> len;
	cin >> n;
	
	for(i=1;i<=n;i++)
		cin >> cut[i];
		
	cut[0] = 0;
	cut[n+1] = len;
	
	for(j=0;j<=n;j++)
		d[j][j+1] = 0;
		
	
	for(i=2;i<=n+1;i++)
	{
		for(j=0;j<=n-i+1;j++)
		{
			d[j][j+i] = 0x7fffffff;
			for(k=j+1;k<j+i;k++)
			{
				if(d[j][k] + d[k][j+i] + cut[j+i] - cut[j] < d[j][j+i])
					d[j][j+i] = d[j][k] + d[k][j+i] + cut[j+i] - cut[j];
			}
		}
	}
	
	cout << d[0][n+1];
}