아래와 같은 20×20 격자가 있습니다.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다. 그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=11)
접근
20×20 그리드 혹은 행렬에서 가로, 세로, 대각선 방향으로 연속한 숫자들을 구해서 그 곱을 계산하고, 이렇게 계산한 4개 숫자의 곱들 중에서 최대값을 구하는 문제이다. 누적곱을 계산하는 함수는 reduce() 와 같은 함수를 이용하면 간단하게 만들 수 있는데, 어떤 식으로 특정한 방향으로 연속한 숫자들을 구하는 방법을 어떻게 만들 수 있을까?
가장 흔히 생각하는 방법은 그리드를 2차원 배열로 생각하는 것이다. 그리드 내 특정한 지점의 좌표를 (행, 열)로 나타낸다고 할 때, 위치 (i, j)에서 각 방향으로 연속한 4개의 값은 다음과 같이 구할 수 있다.
grid = [[int(x) for x in line.split()] for line in s.splitlines()]
i, j = (6, 7)
# 가로 방향 4개, 단, 0 <= i < 17
ws = grid[i][j:j+4]
# 세로 방향 4개. 단 0 <= j < 17
xs = [grid[i+k][j] for k in range(4)]
# 오른쪽아래 대각선. 0 <= i, j < 17
ys = [grid[i+k][j+k] for k in range(4)]
# 왼쪽 아래 대각선 2 < i, j < 17
zs = [grid[i+k][j-k] for k in range(4)](i, j)가 (0, 0) ~ (19, 19)의 범위일 때, 각 방향의 연속된 네 숫자를 구하기 위한 행, 열 번호의 범위에 있을 때 각 방향의 연속된 숫자를 얻을 수 있다. 이렇게 하나의 위치에서 얻을 수 있는 가장 큰 곱을 구한 후, 다시 전체 위치에서의 ‘최대곱’ 중 가장 큰 값을 구하면 된다.
누적곱을 구하는 함수는 reduce() 함수를 사용하여 다음과 같이 간단히 만들 수 있다.
from functools import reduce
def prod(xs):
return reduce(lambda x, y: x * y, xs, 1)전체 코드는 다음과 같다.
from functools import reduce
s = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"""
grid = [[int(x) for x in line.splie()] for line in s.splitlines()]
def prod(xs: list[int]) -> int:
return reduce(lambda x, y: x * y, xs, 1)
def get_max_prod(i, j):
p1 = prod(grid[i][j:j+4]) if j < 17 else 0
p2 = prod(grid[i+k][j] for k in range(4)) if i < 17 else 0
p3 = prod(grid[i+k][j+k] for k in range(4)) if i < 17 and j < 17 else 0
p4 = prod(grid[i+k][j-k] for k in range(4)) if 2 < i < 17 and j < 17 else 0
return max(p1, p2, p3, p4)
def solve():
print(max(get_max_prod(i, j) for i in range(20) for j in range(20)))
%time solve()그리드를 1차원 배열로 사용하기
그리드를 항상 2차원 리스트로만 사용해야 하는 것은 아니다. 2차원 리스트로 표현된 그리드는, 길이가 그리드의 폭과 같은 값으로 일정한 리스트의 리스트이다. 따라서 1차원 리스트를 사용해서도 충분히 표현할 수 있다. 20×20 그리드는 1×400 의 리스트를 사용해서 표현해도 된다. 다만 (i, j) 의 위치에 해당하는 값이 몇 번째 요소인지만 계산할 수 있으면 되는데, 이는 그리드의 폭에 의해서 결정된다.
한 행에 width 개 만큼의 원소가 있기 때문에 아래로 1행씩 내려가면, 인덱스는 width 만큼 늘어나며, 오른쪽으로 1씩 움직이면 인덱스는 1씩 올라간다. 이 성질을 활용하면 대각선 방향으로도 쉽게 진행할 수 있다. width + 1 만큼 움직이면 오른쪽 아래, width - 1 만큼 움직이면 왼쪽 아래로 이동하는 셈이 된다.
(i, j) -> grid[i * 20 + j]의 꼴로 표시하여 얻을 수 있다.- 편의상,
pos = i * 20 + j라 한다면 - 오른쪽 방향으로 4개의 원소 :
grid[pos:pos+4]로 구할 수 있다. - 아래쪽 방향으로 4개의 원소 :
grid[pos:pos+60:20]으로 구할 수 있다. - 오른쪽 아래 방향의 대각선 방향으로는 21씩 늘어나면 된다 :
grid[pos:pos+70:21] - 왼쪽 아래 방향의 대각선은 19씩 늘어나면 된다. :
grid[pos:pos+70:19]
이처럼 그리드를 1차원 배열로 사용하면 모든 방향의 연속된 값들을 모두 똑같은 꼴의 슬라이싱 문법을 사용해서 추출할 수 있다. 실제로 행렬을 다룰 수 있게 해주는 여러 라이브러리들은 다차원 행렬을 이와 같은 방식으로 액세스하도록 내부적으로 구현한다. 대표적으로 numpy가 있다. 어? 그렇다면 numpy를 사용하면 손쉽게 이 문제를 풀 수 있다는 의미 아닐까?
numpy를 사용한 풀이
20×20 크기의 2차원 배열을 사용하여 보다 간단하게 처리는 방법으로는 numpy를 사용하는 방법이 있다. numpy 2차원배열은 행렬처럼 다루기 쉽고, 행방향, 열방향의 합이나 곱을 편하게 계산할 수 있으며, 4×4 크기의 부분열로 쉽게 쪼갤 수 있다.
np.prod(xs, axis=): 열방향이나 행방향으로의 곱을 계산할 수 있다. axis=0 이면 가로, 1이면 세로 방향np.diag(xs): 대각선 벡터를 구한다.np.rot90(xs): 90도 회전한 행렬을 구합니다. 따라서np.diag(np.rot90(xs))라고 하면 오른쪽위에서 왼쪽 아래로 내려오는 대각선을 쉽게 구할 수 있다.
이상의 기능을 사용하면 아래와 같이 get_max_prod 함수를 작성할 수 있다. 이 함수는 4×4 행렬에서 가로, 세로, 대각선의 방향의 숫자들의 곱을 모두 구하고 그 중 가장 큰 값을 리턴한다. 이것을 20×20 행렬에서 얻을 수 있는 모든 4×4 부분행렬에 적용한 후 최대값을 구하면 된다.
import numpy as np
xs = np.array([[int(x) for x in line.split()] for line in s.splitlines()])
ys = [xs[i:i+4, j:j+4] for i in range(17) for j in range(17)]
def get_max_prod(ws):
a = max(np.prod(ws, axis=0))
b = max(np.prod(ws, axis=1))
c = np.prod(np.diag(ws))
d = np.prod(np.diag(np.rot90(ws)))
return max(a, b, c, d)
print(max(map(get_max_prod, ys)))