오일러 프로젝트 18 (Julia)

숫자로 쌓아올린 삼각형에서 내려가면서 인접한 숫자와 더한 값이 최대가 되는 경우를 구하는 문제. 위에서부터 각각의 가능한 경로를 계산하는 식으로 구하면 모든 가능한 경로를 더해야 한다. 각 위치에서 더할 값은 2가지 경우가 있기 때문에 n 줄이 있는 경우에 2^n 만큼의 가능한 경우가 있다. 물론, 이 문제는 줄의 수가 적은 편이라 모든 가능한 경우를 다 더해도 상관없다.

lines = [[1], [2, 3], [4, 5, 6]] 과 같은 값이 있을 때 2에서 더할 수 있는 다음 값은 다음 번 라인의 같은 위치에 있는 값 4와, 그 오른쪽에 있는 값 5이다. 이런 식으로 더해나가서 더 큰 값을 취하도록하는 계산은 재귀를 통해서 구현할 수 있다.

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
    """

# 각 라인별로 자른 후, 각 라인을 공백으로 잘라서 정수로 변환한다.
xs = split(strip(s), "\n") .|> split .|> x -> parse(Int, x)

# i번째 위치와 그 다음 값을 더한 것 중에서 더 큰 값을 취하는 함수
get_maxsum(lines, i=1) = begin
  length(lines) == 1 && return lines[1][i]
  return lines[1][i] + max(get_maxsum(lines[2:end], i), get_maxsum(lines[2:end], i+1))
end

@time get_maxsum(xs) |> println

그런데 문제에서도 이런식으로 푸는 것도 가능하지만, 숫자가 많아지면 어려워진다는 언급이 있고, 실제로 67번 문제는 99줄이나 되어 시간이 너무 오래 걸리게 된다. 따라서 다른 접근법이 필요하다.

위에서 부터 더 합산해 내려가면서 최대값만 유지한다면 어떻게 될까? 처음 두 라인을 합쳐보자.

75
95 64

--> (75+95) (75+64) => 170 139

다음 라인과 합쳐보자

170  139
17   47   82
-->  187  217  221

17에는 170과 139가 더해질 수 있는데, 그 중 큰 값은 170이므로 187이 된다. 47 역시 170과 139를 더할 수 있고 합산하여 큰 값을 취하면 217이다. 82에는 139만 더할 수 있으므로 221이 된다.

따라서 각 라인이 이런 식으로 접힌다고 생각했을 때, 어떤 라인까지의 최대합으로 구성된 라인과 그 다음 라인에서의 각각의 합산이 가능한 것 중 최대값을 더해서 내려가면 마지막 라인은 모두 그 위치까지 오는 경로에서의 최대값이 될 것이다. 이런 식으로 누적하여 특정 라인까지의 경로합의 최대치를 누적해나갈 수 있다.

for (i, line) in enumerate(xs[1:end-1])
  for (j, value) in enumerate(xs[i+1])
      xs[i+1][j] += maximum(xs[i][(j > 1 ? j - 1 : j):(length(line) >= j ? j : j-1)])
  end
end
xs |> last |> maximum |> println

또 다른 접근법으로는 밑에서부터 위로 올라가는 방식이다. 원리는 바로 위의 방법과 같다. 특정 라인의 바로 윗줄이 각 경로의 최대합으로 구성됐다고 가정하고 좌/우 값을 합산하여 큰 값만 취한다. 이런 방식으로 거슬러 올라가면 마지막에는 최대값만 남게 된다.

xs = split(s, "\n") .|> x -> split(x) .|> y -> parse(Int, y)
res = xs[end]
for i=1:length(xs)-1
    left = zip(res, xs[end-i]) .|> sum
    right = zip(res[2:end], xs[end-i]) .|> sum
    res = zip(left, right) .|> maximum
end
res |> first |> println