음... 어데서 가져온 문제입니다. 출처는 나중에 올리겠습니다.
---------------------------------------------------------
[삼각수란?]
얼마전 올린 삼각수 문제에 간단히 설명해 뒀습니다.
http://cbuilder.borlandforum.com/impboard/impboard.dll?action=read&db=bcb_tip&no=964
[문제설명]
다음과 같은 삼각수가 있다고 할때..
3
7 5
2 4 6
8 5 9 3
위에서 부터 시작해서 아래 ROW 에 가까이에 있는 숫자를 따라서 내려올때
그 숫자들의 합이 가장 큰수를 찾는것이 문제입니다.
위 삼각수의 경우
첫번째 row 3 에서는 7 과 5 두가지 길이 있구..
두번째 row 7에서는 다시 세번째 row의 2와 5 두 갈래 길이 있습니다.
이런식으로 내려올때 가장 큰수는 ( 3+ 7 + 4 + 9 ) = 23 입니다.
4개 row에서 나오는 경우의 수는 2^(n-1) 즉 2^3 = 8 가지가 되네요
[문제]
자 문제입니다.
다음과 같이 25개 row로 된 삼각수에서 위에서 아래로 근접한 숫자를 따라 내려오면서
그 숫자들의 합이 가장 큰 수를 찾으세요
64
45 63
75 09 91
15 72 84 86
88 02 72 19 22
28 35 37 80 41 57
10 60 31 25 20 24 92
12 71 56 48 04 39 51 04
45 20 15 19 08 32 01 15 85
27 66 98 14 22 58 14 20 73 18
18 87 60 14 82 55 98 03 24 34 84
09 48 56 50 33 35 45 62 85 33 07 31
44 91 55 47 38 06 52 53 51 02 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 01 63 30 86 91
23 86 39 97 41 42 67 52 82 34 66 58 87 73 08 73 43
33 84 07 75 58 60 47 76 13 55 16 41 36 53 38 45 37 38
50 35 05 44 26 51 51 46 24 72 71 63 66 85 34 93 43 81 97
70 32 76 47 46 59 55 57 01 67 43 83 72 21 01 77 17 35 44 22
90 21 88 97 56 70 24 71 21 48 05 11 85 28 71 24 35 35 96 21 44
32 58 05 09 12 29 87 03 30 01 24 65 52 28 80 05 36 01 21 32 26 36
25 21 85 01 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 05 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 06 26 89 43 90 92
row가 25개 이니 경우의 수는 2^(24) = 16777216 가지가 되겠네요
2^(24)승 돌려봐도 좋구, 눈으로 찾아도 좋은데..
뭐 깔쌈한 알고리즘 없을까요?
그럼..
|
