[Project Euler] Problem 67

원문: Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2 ^ 99 altogether! If you could check one trillion (10 ^ 12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

아래 삼각형의 꼭대기에서 시작해서 행의 인접한 수들로 움직일 때, 꼭대기부터 바닥까지 가장 큰 총합은 23이다.

3
7 4
2 4 6
8 5 9 3

즉, 3 + 7 + 4 + 9 = 23 이다.

triangle.txt (우클릭하여 '다른 이름으로 저장...') 에 있는 삼각형에 대해서 꼭대기부터 바닥까지 가장 큰 총합을 찾아라. 이 파일은 15KB 텍스트 파일이고, 100개 행을 가진 삼각형이 포함되어 있다.

참고: 이것은 Problem 18번의 매우 어려운 버전이다. 이 문제를 풀기 위해 모든 경로인 2^99 개를 시도해보는 것은 불가능하다. 만약, 매 초마다 1조(10 ^ 12) 개의 경로를 확인할 수 있다면, 그것 모두를 확인하기 위해 200억년이 걸린다. 이것을 풀기 위한 효율적인 알고리즘이 있다. ;o)

Problem 18번과 똑같은 프로그램을 이용해서 풀었다.

Python

#! /usr/bin/env python3

data = open("input.txt", "r")

tree = []
row = 0 # 행 개수
for line in data:
    tree += [int(x) for x in line.rstrip('\n').split(' ')]
    row += 1

data.close()

while row > 0:
    row -= 1 # 마지막 행의 윗 행부터 시작
    first = (row - 1) * row // 2 # 그 행의 첫번째 인덱스
    for i in range(row):
        right = tree[first + i + row + 1]
        left = tree[first + i + row]
        tree[first + i] += right if right > left else left

print(tree[0]) # 루트가 가장 큰 값

접기