오일러 프로젝트 67

오일러 프로젝트 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번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경로의 수가 모두 2^{99}이나 되기 때문입니다. 일 초에 1조(10^{12})개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 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])