오일러 프로젝트 18번 문제는 숫자 피라미드를 내려가면서 더했을 때 나올 수 있는 최대합을 계산하는 문제이다. 위에서 아래로 내려가면서 합을 구하고 경로별로 비교하는 전수검사 대신에 다른 방식으로의 접근이 요구된다.
> 다음과 같이 삼각형 모양으로 숫자를 배열했습니다.
3 7 4 2 4 6 8 5 9 3삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다. 다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.
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참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다. 하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.
검토
가능한 모든 경로의 합을 구해보는 것도 시간이 많다면 뭐 얼마든지 할 수 있는 일이지만, 문제에서 언급되었듯이 이 방식으로 푸는 것이 이 문제는 가능하나, 동일한 구조이면서 규모가 훨씬 큰 67번 문제의 경우에는 지금 왠만한 PC 사양으로는 태양의 남은 수명보다도 더 긴시간동안 계산을 해야한다.
따라서 위에서부터 아래로 내려오는 것이 아니라 아래에서부터 위로 올라가면서 가능한 경로의 최대합을 유지해나가는 것이다.
- 먼저 맨 아래줄의 숫자 리스트를 가지고 시작한다.
- 이 숫자 리스트의 각 숫자는 바로 윗줄의 숫자에서 이웃할 수 있는 수와 더해질 수 있다. 따라서 맨 아래줄의 i 번째 숫자 Ni 는 바로 윗줄 M의
혹은
과 더해질 수 있다. 이렇게 더한 두 값 중에 큰 값을 남기고 작은 값은 버린다.
- 2.의 과정을 반복하면서 윗줄로 올라간다. 그 후 맨 윗줄의 값을 처리하고 나면 단 하나의 값이 남게되며, 이 값이 가장 큰 값을 만드는 경로를 취한 결과가 된다.
파이썬 풀이
현재줄을 current_list, 윗줄을 next_list 라 했을 때, 같은 열 끼리 더한 결과와 다음열에 더한 결과를 조합한 후 큰 것만을 남긴다. 이는 현재줄이 1개 더 길기 때문에 오프셋을 준 부분열과 윗줄을 합친다.
current_line = [4, 62, 98, ... 4, 23 ]
next_line = [63, 66, 4, 68 ..., 40, 31]
l1 = [x[0] + x[1] for x in zip(next_line, current_line)]
## ^^^^^^^^^^^ 튜플의 두 원소의 합이기 때문에 sum()으로 대체 가능하다.
l2 = [sum(x) for x in zip(next_line, current_line[:1])]
current_line = [max(x) for x in zip(l1, l2)전체 코드는 다음과 같다.
s = """ 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
"""
data = [[int(x) for x in line.split()] for line in s.splitlines()][::-1]
current_line = data[0]
for next_line in data[1:]:
l1 = [sum(x) for x in zip(next_line, current_line)]
l2 = [sum(x) for x in zip(next_line, current_line[1:])]
current_line = [max(x) for x in zip(l1, l2)]
print(current_line[0])Swift 풀이
Swift에서도 동일한 로직으로 처리한다. 단, Zip 객체는 배열이 아니기 때문에 매 이터레이션마다 배열 객체를 따로 생성해야 한다. 또한 뒤집은 객체 (.reversed()사용)의 경우에 이는 배열의 사본이 아닌 뒤집힌 뷰이기 때문에 정수를 인덱스로 참조할 수 없다.
이 부분만 유의하면 간단하게 처리할 수 있다. 코드는 Swift 4.0 기준으로 재작성했다.
import Foundation
let s = """
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
"""
let data = s.split(separator:"\n").map{
$0.split(separator:" ").flatMap{ Int($0) }
}.reversed()
var current_line = data.first!
for line in data[data.index(after:data.startIndex)...] {
let l1 = zip(line, current_line[..<(current_line.count - 1)])
.map{ $0.0 + $0.1 }
let l2 = zip(line, current_line[1...]).map{ $0.0 + $0.1 }
current_line = Array(zip(l1, l2).map(max))
}
print(current_line.first!)