프로젝트 오일러 18
삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기
문제를 언듯 보면 합이 최대가 되는 경로를 찾아야 할 것 같지만, 명시적으로 경로를 구하지 않더라도 경로의 합이 최대가 되는 값을 찾을 수 있다.
알고리즘
삼각형 꼭데기에 서 있다면 왼쪽 또는 오른쪽으로 내려갈 수 있다. 합이 최대가 되는 경로로 가려면 왼쪽으로 갔을 때의 합이 큰지 오른쪽으로 갔을 때의 합이 큰지 알아야 한다. 합이 최대가 되는 경로에 있는 숫자의 합을 그 삼각형의 최대합이라 한다면, 왼쪽 삼각형의 최대합이 큰지 오른쪽 삼각형의 최대합이 큰지 알아야 한다.
오른쪽 삼각형과 왼쪽 삼각형의 꼭데기에서도 마찬가지다. 다시 말해 왼쪽으로 갈지 오른쪽으로 갈지를 결정하려면 그 아래 단계에 있는 삼각형의 최대합을 구할 수 있어야 한다. 아래 단계의 삼각형 역시 여러 층으로 되어 있다면 바로 최대합을 구할 수 없다. 계속해서 아래 단계로 내려가 거의 바닥까지 내려가면 아래 단계 삼각형이 이층 삼각형이 된다.
이층 삼각형이라면 왼쪽으로 갔을 때의 합과 오른쪽으로 갔을 때의 합을 바로 구할 수 있다. 맨 아래 단계에 있는 각 삼각형에 대해 왼쪽 합과 오른쪽의 합을 구해 큰 값을 꼭데기에 쓴다면 다음 그림과 같이 될 것이다. 맨 아래층은 더 이상 필요하지 않으므로 지울 수 있다.
다시 맨 아래 두 층에 대해서 같은 작업을 반복한다. 이런 식으로 밑에서부터 왼쪽 합과 오른쪽 합 중 큰 값을 계속해 위로 올리는 식으로 작업할 수 있다.
계속 올라가다보면 결국 맨 위 두 층만 남을 것이다. 여기서 왼쪽과 오른쪽의 합 중 큰 값을 구하면 그 값이 합이 최대가 되는 경로의 합이 된다.
코드
다음 그림과 같이 맨 아래층과 그 위층의 숫자에 대해 한 번은 왼쪽으로, 또 한 번은 오른쪽으로 더한 다음 큰 값을 구하는 작업을 반복해 문제를 풀 수 있다.
각 층을 vector로 표현하면, 위 그림의 맨 아래층은 [8 5 9 3]으로, 그 윗층은 [2 4 6]으로 나타낼 수 있다.
user=> (def ls [8 5 9 3]) #'user/ls user=> (def us [2 4 6]) #'user/us
왼쪽으로 갔을 때의 합과 오른쪽으로 갔을 때의 합은 다음과 같이 간단히 구할 수 있다.
user=> (map + ls us) (10 9 15) user=> (map + (rest ls) us) (7 13 9)
그리고 두 합 중 큰 값은 다음과 같이 구할 수 있다.
user=> (map max *1 *2) (10 13 15)
이걸 다음과 같이 함수로 만들 수 있다.
(fn [ls us] (map max (map + ls us) (map + (rest ls) us)))
위 함수를 맨 아래 층과 그 위층에 적용하고, 그 결과와 바로 위층에 적용하며 위로 올라가야 한다. 이런 작업에는 reduce를 사용하는 것이 알맞다. 따라서 다음과 같이 find-max 함수를 정의할 수 있다.
(defn find-max [t]
(reduce (fn [ls us] (map max (map + ls us) (map + (rest ls) us))) t))
이제 문제를 다 푼 것과 마찬가지다. 삼각형은 다음과 같이 vector의 vector로 정의할 수 있다. 삼각형의 밑에서부터 올라가며 작업해야 한다. fold-right가 있다면 좋겠지만 Clojure 기본 함수에는 fold-right가 없으므로 reverse한 후 reduce 하면 같은 효과를 얻을 수 있다. 여기서는 계산 편의를 위해 미리 reverse 해 두었다.
(def triangle
(reverse
[[75]
[95 64]
[17 47 82]
[18 35 87 10]
[20 4 82 47 65]
[19 1 23 75 3 34]
[88 2 77 73 7 63 67]
[99 65 4 28 6 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 4 68 89 53 67 30 73 16 69 87 40 31]
[ 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23]]))
find-max 함수에 triangle을 인자로 주어 호출하면 답을 구할 수 있다.
(defn solve []
(find-max triangle))
실행 결과는 다음과 같다.
p018=> (time (solve)) "Elapsed time: 0.382559 msecs" (1074)
참고
- 프로젝트 오일러 18 풀이 소스 코드
- 프로젝트 오일러 67 같은 문제다. 여기서는 삼각형이 15층에 불과했지만, 이 문제에서는 100층짜리 삼각형을 다뤄야 한다.