오일러 프로젝트 11번 – 격자내에서의 이웃한 네 수의 곱의 최대값 찾기
이번 문제는 격자를 탐색하는 문제이다.
아래와 같은 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 <span style="color: #ff0000;">26</span> 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 <span style="color: #ff0000;">63</span> 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 <span style="color: #ff0000;">78</span> 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 <span style="color: #ff0000;">14</span> 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)
접근
문제를 액면 그대로 받아들이면, 20X20의 격자에 각 정수가 있는 그리드에서 특정한 방향으로 4개씩의 정수를 뽑아서 곱하고, 그 결과 중에서 최대값을 찾도록 하는 것이다. 그래서 포럼등에서 다른 사람들의 풀이를 보면 열에 아홉은 2차원배열을 많이 쓰더라. 그런데 개인적으로 2차원 배열을 쓰는 걸 아주 싫어해서 이런 그리드 문제는 1차원 배열(리스트)로 푸는 것을 좋아한다.
그리드를 1차원 배열로 사용하기
그리드를 1차원 배열을 써서 사용하는 것은 사실상 아무런 문제가 없다. 그리드에서 특정한 한 칸을 표현하기 위해서는 열, 행의 두 가지 좌표 값이 필요하나, 1차원 배열은 인덱스값 하나면 된다. 그런데 가로와 세로 크기가 정해진 그리드라면 1차원 배열로 표현하는데 아무런 문제가 없다. 아래 그리드는 10X10에서의 특정한 좌표를 표현하고 있다. 셀 p 가 위치한 곳의 좌표는 [2행, 4열]인데 (이 때, 각 행과 열은 0부터 시작함) p의 인덱스는 24이다.
p의 위쪽으로는 20개의 셀(2개 행)이 있고, p의 왼쪽으로는 4개의 셀(4열)이 있다. 따라서 셀 P의 위치는 P의 인덱스가 p라고 할 때, 다음과 같이 표현할 수 있다.
0 1 2 3 4 5 6 7 8 9 0 * * * * * * * * * * 1 * * * * * * * * * * 2 * * * * p * * * * * 3 * * * * * * * * * * 4 * * * * * * * * * * 5 * * * * * * * * * * 6 * * * * * * * * * * 7 * * * * * * * * * * 8 * * * * * * * * * * 9 * * * * * * * * * *
- 셀P의 행 : p를 폭(10)으로 나눈 몫
- 셀P의 열 : p를 폭으로 나눈 나머지
그외에 전체 데이터를 data라는 리스트라고 두면,
- n번째 행은
data[n*width:(n+1)*width]로 얻을 수 있고, - n 번째 열은
[data[n + i * width] for i in range(height)]로 얻을 수 있다.
풀이
아래는 위 그리드의 일부분인데, 숫자 23을 주목해보자. 이 위치에서 숫자 4개의 곲을 찾을 수 있는 방향은 총 4개로 가로(오른쪽)방향, 세로(아래)방향, 대각선(오른쪽아래 및 왼쪽아래)방향 두 곳이다.
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 ....
그런데, 모든 위치에서 네 방향의 숫자곱을 구할 수는 없다. 예를 들어 초록색으로 표시한 89의 경우에는 오른쪽으로 숫자곱을 3개까지만 만들 수 있으므로 가로 및 우하단 방향 대각선을 구할 수 없을 것이다. 따라서 임의의 점 P에서 구할 수 있는 숫자곱의 경우와 이 때, 인덱스가 각각 증가해야 하는 범위들은 다음과 같다.
- 가로 : 열 위치가 0~16일때. 인덱스를 1씩 올려준다.
- 세로 : 행 위치가 0~16일때. 인덱스를 20씩 올려준다.
- 우하단: 열위치가 0~16이고, 행 위치도 0~16일 때. 인덱스를 21씩 올려준다.
- 좌하단: 열 위치가 3~19이고, 행 위치는 0~16일 때. 인덱스를 19씩 올려준다.
모든 숫자값 중에서 음수는 없으므로 모든 곱은 0이상이 될 것이므로, 특정 위치에서 구할 수 없는 값은 0으로 처리하자. 그러핟면 특정 인덱스 p에서 저 네 값을 구해서 그 중 최대값을 구하는 함수는 다음과 같이 정리할 수 있다.
먼저 숫자 리스트의 곱을 구하기 위해서 함수를 하나 간단히 준비한다.
from functools import reduce
def product(arr):
return reduce(lamdba x, y: x*y, arr, 1)다음은 특정 위치(1차원 배열의 인덱스 위치)에서 구할 수 있는 4방향 곱의 최대치를 구하는 함수이다.
def gms(pos):
sum_h = 0 if pos % 20 > 16 else product(data[pos:pos+4])
sum_v = 0 if pos // 20 > 16 else produce((data[pos+20*i] for i in range(4)))
sum_s = 0 if pos % 20 > 16 or pos // 20 > 16 else\
product(data[pos+21*i] for i in range(4)))
sum_t = 0 if pos % 20 < 3 or pos // 20 > 16 else\
product(data[pos+19*i] for i in range(4)))
return max(sum_h, sum_v, sum_s, sum_t)준비가 완료되었다. 이제 주어진 그리드 문자열을 정수배열로 변환한 다음, gms를 적용한 후의 최대값을 찾아보자.
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"""
data = [int(x) for x in s.replace('\n', ' ').split(' ')]
result = max((gms(x) for x in range(len(data)))
print(result)