오일러 프로젝트 67번 문제는 18번 문제와 동일하나 주어지는 데이터의 양이 훨씬 크다. 18번 문제의 경우에는 모든 경로를 계산하는 것이 불가능한 수준은 아니었으나, 이 문제의 가능한 모든 경로는 2^99 가지나 된다. 하지만 우리는 이미 18번 문제를 동적 계획법에 따라 풀어보았고, 이 문제 역시 같은 방식으로 풀어 낼 수 있다.
아래와 같은 삼각형의 꼭대기에서 인저반 숫자를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23으로 가장 큽니다.
3 7 4 2 4 6 8 5 9 3텍스트 파일 triangle.txt에는 100줄짜리 삼각형 숫자 데이터가 들어 있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최대값은 얼마입니까?
참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경로의 수가 모두
이나 되기 때문입니다. 일 초에 1조(
)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리듬을 찾아보시기 바랍니다.
접근
위에서 아래로 내려오는 식으로 계산하는 것은 모든 경로를 다 비교할 수 밖에 없다. N번째 행에서의 선택은 N+2번째에서의 선택 가능한 길을 3개로 제한하기 때문이다. 따라서 위쪽에서 분기하여 계산하고, 다시 다른 분기를 계산해서 비교해야 하는데 이것은 바른 접근이 아니다. 대신에 아래에서 위로 올라가야 한다. 아래에서 위로 올라가면서 각 숫자에 최대합 경로를 통해서 다다랏다고 가정하면서 각 숫자에서 가장 큰 합을 구해나가면 1개의 해로 압축할 수 있다.
Swift 풀이
윗줄이 아랫줄보다 1칸이 적으므로 윗줄의 x 번째 원소와 아랫줄의 x 번째 원소, 그리고 아랫줄의 x + 1 번째 원소를 각각 더한 값 중에서 더 큰 값을 선택한 배열을 남겨둔다. 이 결과는 윗줄의 칸과 같은 칸 수를 가지는 배열이며, 각 원소는 시작점에서 시작하여 각각 최대합 경로를 타고 내려왔을 때의 합을 상정한다. 이 과정을 아래에서 위로 반복한다.
func solve(_ data:[[Int]]) -> Int? {
guard !data.isEmpty else { return nil }
var i = data.count - 1
var currentLine = data[i]
var result = 0
while i > 0 {
let upperLine = data[i - 1]
let p1 = zip(upperLine, currentLine).map{ $0.0 + $0.1 }
let p2 = zip(upperLine, currentLine[1...]).map{ $0.0 + $0.1 }
let currentLine = zip(p1, p2).map{ $0.0 > $0.1 ? $0.0 < $0.1 }
}
return currentLine.first
}그외 코드는 모두 예시 데이터를 읽고 분해하는 과정이다.
import Foundation
main: do {
let data: [[Int]] = {
guard let url = URL(string:"http://euler.synap.co.kr/files/triangle.txt"),
let content = try? String(contentsOf: url)
else { return [] }
let lines = data.split(separator: "\r\n")
let result = lines.map{ line in line.split(separator: " ").flatMap{ Int($0) }}
return result
}()
if let result = solve(data) {
print(result0
}
}파이썬 풀이
Python 3.6
from urllib.request import urlopen
def main():
data = urlopen('http://euler.synap.co.kr/files/triangle.txt').read().decode()
lines = [[int(x) for x in line.split()] for line in data.splitlines()]
current_line = lines[-1]
for line in lines[-1::-1]:
x = [sum(x) for x in zip(line, current_line]
y = [sum(x) for x in zip(line, current_line[1:]]
current_line = [max(*n) for n in zip(x, y)]
print(current_line[0])