몇일전 삼각수열 퀴즈2에 대해..
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=972
바로 아래에 삼각수열 문제 풀이1을 올렸습니다.
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=974
첫번째 방법은 재귀함수를 이용하여 모든 경우의 수 2^(25-1) = 2^24 = 16777216 가지 경우의 수를
모두 확인해 보았는데요..
상당히 많은 시간이 걸렸습니다.
[두번재 풀이 방법]
두번째 풀이 방법은?
첫번째 방법과는 비교도 안될정도로 엄청 빠릅니다.
이 방법은 제 머리에서 나온것이 아니구요..
"C++Builder완전정복" 카페에 올려진 문제에 "Clov"님이 댓글로 답변 다신 방법입니다.
http://cafe.naver.com/bcbmaster/1123
설명드리면
다음과 같은 삼각수에서...
3
7 5
2 4 6
8 5 9 3
//위에서 부터 한줄씩 계산을 해 내려가는데..
첫번째 컬럼과 마지막 컬럼은 그냥 현재값과 위쪽row의 값을 더해서 더한값으로 교체합니다.
3
10 8 <-----덧셈을 해서 숫자를 바꿈
2 4 6
8 5 9 3
세번째 row에서는..
3
10 8
12 4 14 <<-----------첫번째와 마지막을 윗쪽row의 값을 더해서 교체함
8 5 9 3
세번재 row의 중간값은?
3
10 8 <-----덧셈을 해서 숫자를 바꿈
12 14 14 << 4위치에느 10+4 와 8+4 중 큰값인 14를 넣음
8 5 9 3
//위와같은 방식으로 마지막 라인도 값을 계산하면..
3
10 8
12 14 14
20 19 23 17 <== 다음과 같이 되겠죠?
위 4-row의 삼각수에서 합의 최대값은 23 이 됩니다.
[코딩]
아래 문제의 25개 row값을 가지고 계산하는 코드를 짜 보았습니다.
// 삼각수열 배열
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 GetVal(int *Tmp,int col,int row)
{
if(col>=0 && col<=row)
return Tmp[(row*(row+1))/2+col];
else return 0 ;
}
//---------------------------------------------------------------------------
void SetVal(int *Tmp,int col,int row,int val)
{
if(col>=0 && col<=row)
Tmp[(row*(row+1))/2+col]=val;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
int *Tmp=new int [sizeof(Numbers)];
memcpy(Tmp,Numbers,sizeof(Numbers));
for(int row=1;row<25;row++)
{
for(int col=0;col<=row;col++)
{
if(col==0)
{
SetVal(Tmp,0,row,GetVal(Tmp,0,row-1)+GetVal(Tmp,0,row));
}
else if(col==row)
{
SetVal(Tmp,col,row,GetVal(Tmp,col-1,row-1)+GetVal(Tmp,col,row));
}
else
{
int iTmp1=GetVal(Tmp,col-1,row-1)+GetVal(Tmp,col,row);
int iTmp2=GetVal(Tmp,col,row-1)+GetVal(Tmp,col,row);
if(iTmp1>iTmp2) SetVal(Tmp,col,row,iTmp1);
else SetVal(Tmp,col,row,iTmp2);
}
}
}
int iMaxVal=0;
for(int col=0;col<25;col++)
{
int val=GetVal(Tmp,col,24);
if(val>iMaxVal)iMaxVal=val;
}
delete Tmp;
ShowMessage(iMaxVal);
}
//---------------------------------------------------------------------------
첫번째 풀이는 한참을 1초가량 걸렸었는데..
위 방식은 엄청 빠르네요..
그럼..
