오일러 프로젝트 67

아래와 같은 삼각형의 꼭대기에서 인접한 수를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23 으로 가장 큽니다.

텍스트 파일 triangle.txt에는 100줄짜리 삼각형 수 데이터가 들어있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최댓값은 얼마입니까?

참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 2⁹⁹나 되기 때문입니다. 일 초에 1조(10¹²)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리듬을 찾아보시기 바랍니다.

https://euler.synap.co.kr/problem=67

사실 18번 문제의 풀이에서도 67번을 언급하면서 다른 방법을 적용하여 더 빨리 계산할 수 있다고 했다. 맨 아랫줄부터 거꾸로 계산하는 것이다. 맨 아랫줄의 윗줄의 각 값이, 사실은 해당 위치로 도달하는데 있어 최대의 합이된 상태라고 가정하는 것이다. 그러면 윗줄의 각 값이 아랫줄의 값과 더해진 결과 중에서 큰 쪽을 취한다.

이렇게 계산하면 맨 아랫줄이 제거되면서 최대값의 후보가 하나 줄어든다. (줄이 올라갈 수록 길이가 1씩 짧아지므로) 같은 방식으로 첫번째 줄까지 반복하면 최종적으로는 최대합만 남게 된다.

이 문제가 18번과 다른 점은 결국 urllib 을 사용해서 원격 파일을 열어서 읽는다는 것 말고는 없다.

from urllib.request import urlopen

def solve():
  data = urlopen("https://euler.synap.co.kr/files/triangle.txt").read().decode()
  triangle = [[int(x) for x in line.split()] for line in data.splitlines()]
  current = triangle[-1]
  for upper_line in lines[-1::-1]:
    lhs = [sum(x) for x in zip(upper_line, current)]
    rhs = [sum(x) for x in zip(upper_line, current[1:])]
    current = [max(x) for x in zip(lhs, rhs)]
  print(current[0])

if __name__ == "__main__":
  solve()