아래에
삼각수열 알고리즘 문제를 내었는데...
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=971
Frigate님께서 답변해주셨네요
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=972
사실 Frigate님 코드가 잘 이해가 안되지만..
결과는 저랑 같네요..
[풀이1]
예전에 이문제를 접한적이 있었는데..
그때 다음과 같이 풀었었네요
// 삼각수열 배열
int Numbers[] = {
64,
45, 63,
75, 9, 91,
15, 72, 84, 86,
88, 2, 72, 19, 22,
28, 35, 37, 80, 41, 57,
10, 60, 31, 25, 20, 24, 92,
12, 71, 56, 48, 4, 39, 51, 4,
45, 20, 15, 19, 8, 32, 1, 15, 85,
27, 66, 98, 14, 22, 58, 14, 20, 73, 18,
18, 87, 60, 14, 82, 55, 98, 3, 24, 34, 84,
9, 48, 56, 50, 33, 35, 45, 62, 85, 33, 7, 31,
44, 91, 55, 47, 38, 6, 52 ,53, 51, 2, 84, 24, 60,
30, 53, 87, 92, 96, 95, 59, 02, 13, 32, 11, 85, 74, 37,
54, 10, 60, 29, 59, 73, 57, 97, 92, 85, 20, 45, 77, 75, 36,
56, 88, 29, 37, 96, 64, 39, 20, 29, 43, 95, 1, 63, 30, 86, 91,
23, 86, 39, 97, 41, 42, 67, 52, 82, 34, 66, 58, 87, 73, 8, 73, 43,
33, 84, 7, 75, 58, 60, 47, 76, 13, 55, 16, 41, 36, 53, 38, 45, 37, 38,
50, 35, 5, 44, 26, 51, 51, 46, 24, 72, 71, 63, 66, 85, 34, 93, 43, 81, 97,
70, 32, 76, 47, 46, 59, 55, 57, 1, 67, 43, 83, 72, 21, 1, 77, 17, 35, 44, 22,
90, 21, 88, 97, 56, 70, 24, 71, 21, 48, 5, 11, 85, 28, 71, 24, 35, 35, 96, 21, 44,
32, 58, 5, 9, 12, 29, 87, 3, 30, 1, 24, 65, 52, 28, 80, 5, 36, 1, 21, 32, 26, 36,
25, 21, 85, 1, 21, 87, 47, 56, 55, 99, 86, 31, 79, 12, 27, 11, 63, 17, 65, 62, 36, 36, 21,
80, 48, 22, 17, 54, 63, 93, 79, 65, 68, 92, 61, 5, 17, 68, 98, 25, 88, 83, 83, 02, 84, 47, 69,
36, 32, 74, 93, 70, 36, 68, 30, 37, 30, 25, 67, 27, 75, 69, 11, 83, 70, 16, 6, 26, 89, 43, 90, 92
};
//---------------------------------------------------------------------------
int __fastcall GetNum(int col,int row)
{
if(col>=0 && col<=row)
{
int idx=(row*(row+1))/2+col;
return Numbers[idx];
}
throw Exception("Index Out of Bound");
return 0 ;
}
//---------------------------------------------------------------------------
void __fastcall GetMaxValue(int iCol,int iRow,int iSum,int &iOutMax)
{
if(iRow<24)
{
GetMaxValue(iCol,iRow+1,iSum+GetNum(iCol,iRow),iOutMax);
GetMaxValue(iCol+1,iRow+1,iSum+GetNum(iCol+1,iRow),iOutMax);
}
else
{
if(iOutMax < (iSum+GetNum(iCol,iRow)))iOutMax=iSum+GetNum(iCol,iRow);
if(iOutMax < (iSum+GetNum(iCol+1,iRow)))iOutMax=iSum+GetNum(iCol+1,iRow);
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int iOutMax=0;
GetMaxValue(0,1,GetNum(0,0),iOutMax);
ShowMessage("MaxValue="+IntToStr(iOutMax));
}
//---------------------------------------------------------------------------
재귀함수 이용했구요..
그런데 이방식은 2^24승 모두 체크하는 방식입니다.
그래서 시간이 좀 걸리네요 1초정도..
더 좋은 알고리즘은 없을까요?
...
그럼..