프로젝트 오일러 011

문제

11번 문제

20×20 격자에서 연속된 네 수의 곱 중 최댓값

사이냅소프트

문제는 사뭇 간단한데, 개인의 취향에 따라 풀이 방식은 매우 간단할 수 있습니다. 아마 이런 격자를 보면 2중 리스트를 생각하는 사람들도 있을 것이고, 행렬을 생각하는 사람들도 있을 겁니다. (물론 numpy를 사용해서 풀 수도 있겠죠!)

1차원 리스트로 격자 표현하기

개인적으로는 이렇게 폭이 일정한 격자는 그냥 1차원 리스트 그대로 사용하는 것도 나쁘지 않다고 생각합니다. 왼쪽 위를 원점으로, (0, 0) 이라고 치면, 좌표 (w, h)에 해당하는 인덱스는 다음과 같이 결정됩니다. 그렇다면 다시 반대로, 인덱스를 그리드의 폭으로 나누면 몫은 세로(행의 순서)좌표, 나머지가 가로 좌표가 됩니다.

WIDTH = 20
i = h * WIDTH + w

h, w = divmod(i, WIDTH)

즉, 사각형 격자 내에서는 세로 방향의 연속한 요소는 폭 만큼의 인덱스 차이가 나게 됩니다. 그러면 오른쪽 아래와 왼쪽 아래 방향의 요소들은 폭 + 1, 폭 - 1 의 인덱스 차이를 갖습니다.

이 원리를 이용해서 격자 내 i 번째 위치에서 가로, 세로, 우하방, 좌하방으로 4개의 숫자의 곱 중 최대값을 구하는 함수를 작성합니다. 이를 0 ~ 399 범위에 대해서 반복하고 다시 그 중의 최대값을 구하면 됩니다.

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

xs = tuple(map(int, (x.strip() for x in s.split())))
WIDTH = 20
k = 4
prod = lambda xs: reduce(lambda x, y: x * y, xs)

# 특정한 지점에서의 각 방향 4개 숫자의 곱
def f(i: int) -> int:
    res: list[int] = [0]
    h, w = divmod(i, WIDTH)
    if w <= (WIDTH - k):
        res.append(prod(xs[i:i+4]))
    if h <= (WIDTH - k):
        res.append(prod(xs[i + WIDTH * j] for j in range(k)))
        if w >= (k - 1):
            res.append(prod(xs[i+(WIDTH - 1) * j] for j in range(k)))
        if w <= (WIDTH - k):
            res.append(prod(xs[i+(WIDTH + 1) * j] for j in range(k)))
    return max(res)


print(max(map(f, range(len(xs)))))