오일러 프로젝트의 18번과 67번 문제다.

3
7 5
2 4 6
8 5 9 3

위와 같은 숫자로 된 피라미드가 있다. 가장 위쪽에서 가장 아래까지 한칸씩 움직이면서 내려온다. 그리고, 내려오면서 그 경로에 있는 숫자를 모두 더한다. 위에 빨간색으로 표시된 길은 그 합이 최대가 되는 경로에 해당한다.

문제. 다음 숫자 피라미드의 꼭대기에서 밑바닥까지 내려갈 때, 합이 최대가 되는 경로를 지난다고 하면, 그 합의 값은 얼마인가?
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

해설에 의하면, 위의 피라미드는 겨우 16단이고, 따라서 가능한 경우가 16384가지밖에 없다. 따라서 모든 경로를 모두 테스트 하는 것이 가능하다. 그런데, 67번 문제는 좀 더 막장이다.

이건 100줄짜리인데, 2의 100제곱 만큼의 경로가 있다. 이걸 모든 경로를 다 해본다는 것은 사실상 불가능하다. -_-;

즉, 그보다 좀 더 똑똑한 방법을 생각해야 한다.

물론 난 두 문제 모두 알고리즘으로 풀었으므로 이 해설을 쓸 수 있는 거다. 알고리즘만 잘 짜면 펜티엄3 800MHz로도 0.1초만에 답이 나오게 할 수 있다.

힌트
1. 이 문제는 해결한 사람이 매우 많다. 이것은 굉장한 힌트가 된다.
2. 모든 경로를 다 해보는 것은 불가능하다는 사실을 이미 알려주고 있다. 이것으로부터도 많은 것을 깨달을 수 있다.



아무튼, 한번에 2문제를 풀었으니 된거다.
by snowall 2008. 10. 22. 23:44
  • 익명 2008.10.23 10:55 ADDR EDIT/DEL REPLY

    비밀댓글입니다

    • snowall 2008.10.23 12:53 신고 EDIT/DEL

      그렇게 하는 경우, 숫자 하나가 크게 나와 버리면 그때까지 최대값을 따라오던 경로가 갑자기 최대가 아니게 되는 상황이 있을 수도 있습니다. 그런 경우, 최대가 아니게 되는 경로를 계속 따라가게 되므로 원하는 답을 낼 수는 없게 됩니다.

    • goldenbug 2008.10.23 21:24 신고 EDIT/DEL

      풀이하신 것은 좀 이상한데요. 작은 숫자로 고립된 부분에 아주 큰 숫자가 들어있는 경우 snowall님의 방법으로는 안 풀려요. 그냥 조금 큰 숫자들이 있는 곳으로 빙 돌아가게 되는 결과가 나올텐데요....

    • snowall 2008.10.23 22:31 신고 EDIT/DEL

      제 방법은 실질적으로는 "모든" 값을 계산합니다.
      가장 마지막 단계에서, 그때까지 계산된 값 중 최대값을 골라내게 되죠.
      아무래도 제 설명이 부족한 것 같습니다.

    • goldenbug 2008.11.06 08:44 신고 EDIT/DEL

      하하하
      몽땅 계산해서 가장 큰 값의 계보를 추적하는 것이군요. ^^

    • snowall 2008.11.06 09:10 신고 EDIT/DEL

      바로 그겁니다. 모든 경로를 해볼 필요가 없다는 것이 힌트인 것이죠.

  • ㄹㄹㄹ 2008.10.23 15:27 ADDR EDIT/DEL REPLY

    음.. 전산과가 아니셔서 Dynamic Programming에 아마 익숙치 않으셨을 것 같습니다.
    중간에 풀다보면 N*N 숫자 사각형에서 최소경로 찾는 문제가 있습니다.
    이놈이 여러가지 버전으로 계속 응용되면서 어려워지는데 재밌습니다 ㅎㅎ