Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:06Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 12:		Line 12:
	};		};

	Stick stick[51][51];		Stick stick[51][51];

	int stickLen, cuttingTime, cuttingPart, preCutting;		int stickLen, cuttingTime, cuttingPart, preCutting;
Line 24:		Line 24:
	for(i=0,j=stickNum; i<cuttingTime-stickNum+2; i++,j++)		for(i=0,j=stickNum; i<cuttingTime-stickNum+2; i++,j++)
	{		{
	stick[i][j].cost=1000000;		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;		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++)		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)		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;		stick[i][j].cost = stick[i][k].cost + stick[k][j].cost + stick[i][k].len + stick[k][j].len;
	}		}
	stickNum++;		stickNum++;
	}		}
	return stick[0][cuttingTime+1].cost;		return stick[0][cuttingTime+1].cost;
	}		}

Line 46:		Line 46:
	{		{
	cin >> cuttingPart;		cin >> cuttingPart;
	stick[i][i+1].len=cuttingPart-preCutting;		stick[i][i+1].len=cuttingPart-preCutting;
	stick[i][i+1].cost=0;		stick[i][i+1].cost=0;
	preCutting = cuttingPart;		preCutting = cuttingPart;
	}		}
	stick[cuttingTime][cuttingTime+1].len=stickLen-preCutting;		stick[cuttingTime][cuttingTime+1].len=stickLen-preCutting;
	stick[cuttingTime][cuttingTime+1].cost=0;		stick[cuttingTime][cuttingTime+1].cost=0;
	cout << "The minimum cutting is "<<calculate()<<"."<<endl;		cout << "The minimum cutting is "<<calculate()<<"."<<endl;
	}		}
	return 0;		return 0;
	}		}

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:04Z

New page

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

== 소스 ==
#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;
}

CuttingSticks/하기웅 - Revision history

Maintenance script: Repair batch-0001 pages from live compare

imported>Unknown at 05:23, 7 February 2021