다음과 같이 삼각형 모양으로 수를 배열했습니다.
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참고: 여기서는 경로가 16,384개 밖에 안되기 때문에 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다. 하지만 67번 문제에는 100층자리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.
https://euler.synap.co.kr/problem=18
데이터 정리
먼저 데이터를 사용하기 편하게 정리할 필요가 있다. 삼각형 모양의 데이터를 정수의 2중 리스트로 변환한다. 문자열을 각각의 행별로 자른 다음, 각 행의 단어를 다시 자르고 정수로 변환하면 된다.
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"""
triangle = [[int(x) for x in line.split()] for line in s.splitlines()]더 큰 값을 취하는 함수
삼각형 내의 임의의 위치 (i, j) 까지의 경로가 최대 누적합이라고 가정하면, 이 위치에서는 (i + 1, j) 로 진행하거나, (i + 1, j + 1) 으로 진행하는 두 가지 경우가 있을 수 있다. 각각의 경로로 진행했을 때 최대합을 얻고, 그 중에서 큰 값과 (i, j) 에서의 값을 더해주면 임의의 위치로부터 시작했을 때의 최대누적경로를 구할 수 있다. 이것을 첫번째 위치인 (0, 0)에서부터 시작하면 전체의 최대누적합을 구하게 된다.
def helper(i, j):
if len(triangle) > i + 1:
return triangle[i][j] + max(helper(i+1, j), helper(i+1, j+1))
return triangle[i][j] # 맨 마지막 행에 도달했을 때
print(helper(0, 0))좀 더 빠른 방법
그런데 이렇게 재귀를 이용하는 경우에는 실질적으로 모든 경로를 다 방문하여 최대 경로를 구하게 된다. 따라서 같은 방법으로는 67번과 같은 문제는 풀 수가 없다. (100개 행의 경우에는 가능한 모든 경로가 633,825,300,114,114,700,748,351,602,688가지나 된다.) 다른 방법으로는 거꾸로 접근하는 방법을 생각해볼 수 있다.
앞서 재귀를 사용한 해법에서는 아래 행으로 내려간 후에도 계속해서 최대 누적합을 찾을 것이라고 가정했었다. 아래에서부터 위로 올라가보는 것이다.
맨 마지막 줄에는 15개의 숫자가 있고, 바로 윗줄에는 14개의 숫자가 있다. 이 두 줄을 합치는 방법으로는 두 번의 계산을 각각 수행할 수 있다. 이렇게 더해진 값에서 자리에서 더 큰 값을 취하면 15번줄과 14번 줄을 합쳐서 최대 경로만 남기게 된다.
같은 방식으로 이렇게 남긴 14개의 숫자를 13번줄에 대해서도 정리하면 13개의 최대 경로 후보가 남는다. 이를 1번줄까지 거꾸로 반복하면 마지막으로는 최대합 1개만이 남게 될 것이다.
# 모든 값에서 왼쪽 아래로 내려와서 더했다면
# 04 62 98 27 23 09 70 98 73 93 38 53 60 04
# +) 63 66 04 68 89 53 67 30 73 16 69 87 40 31
# 모든 값에서 오른쪽 아래로 내려와서 더했다면
# 62 98 27 23 09 70 98 73 93 38 53 60 04 23
# +) 63 66 04 68 89 53 67 30 73 16 69 87 40 31
zip() 함수를 신날 정도로 많이 사용하면 의외로 코드는 아주 간단하게 마무리된다.
def solve():
triangle = [[int(x) for x in line.split()] for line in s.splitlines()][::-1]
current = triangle [0]
for upper_line in triangle [1:]:
lhs = map(sum, zip(upper_line, current))
rhs = map(sum, zip(upper_line, current[1:]))
current = list(map(max, zip(lhs, rhs)))
print(current[0])
이 동작은 행의 수만큼만 반복하면 되는 연산들이기 때문에 100개 행이 아닌 1,000개나 10,000개 이상의 행에 대해서도 빠르게 처리될 수 있다.