In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
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
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
[출처 - projecteuler.net/]
이번 문제는 가로 / 세로 / 대각선에 대해서 연속하는 4개의 숫자에 대한 곱의 값이 가장 큰 수를 찾아내는 문제입니다. 아무래도 이건 알고리즘보다는 해당 로직에 대한 구현이 가능한지에 대한 문제라고 보여집니다. 따로 최적화는 들어갈 필요는 없어보이고... 혹시 나중에 최적화가 필요한 부분이 있다고 판단되면 추가로 올려보도록 하겠습니다.
1. Basic
우선 크기는 20 x 20에 해당하는 matrix로 전체위치를 한번씩만 순회한다고 하면 O(n^2) 인 400번의 탐색이 일어나게 됩니다. 그리고 각 탐색조건마다 아래의 4가지에 대해서 연산이 필요하게 되겠죠.
- 가로에 해당하는 해당 위치에서 오른쪽으로 0칸 ~ 3칸
- 세로에 해당하는 해당 위치에서 아래쪽으로 0칸 ~ 3칸
- 대각선 중 우측대각선에 해당하는 해당 위치에서 우측+아래 0칸 ~ 3칸
- 대각선 중 좌측대각선에 해당하는 해당 위치에서 좌측+아래 0칸 ~ 3칸
그렇게 되면, 아래의 연산량이 필요하게 됩니다. O(n^2) x 4 x 4... 따라서 총 6,400번의 탐색 및 연산이 일어나게 되고... 최대 10^4 이라고 가정하면 1초보다 한참 적은 시간이 소요되어 결과가 나올 것 이라고 예상이 가능합니다.
저는 보통 일반적인 PC를 기준으로 10^8 정도의 반복 연산이 일어날 경우 1초라고 가정하고 문제를 대합니다. 성능이 좋으면 10^9도 물론 가능할 것 입니다.
그렇다면 각 경우에 대해서 순회가 가능하도록 코드를 구현해 보겠습니다.
[소스 코드]
import time
def MaxMat(mat):
res = 0
for i in range(20):
for j in range(20):
# to the right
temp = 1
for n in range(4):
if j+n >= 20:
temp = 0
break
temp *= mat[i][j+n]
if temp > res:
temp, res = res, temp
# to the bottom
temp = 1
for n in range(4):
if i+n >= 20:
temp = 0
break
temp *= mat[i+n][j]
if temp > res:
temp, res = res, temp
# to the forward diagonal
temp = 1
for n in range(4):
if i+n >= 20 or j+n >= 20:
temp = 0
break
temp *= mat[i+n][j+n]
if temp > res:
temp, res = res, temp
# to the backward diagonal
temp = 1
for n in range(4):
if i+n >= 20 or j-n < 0:
temp = 0
break
temp *= mat[i+n][j-n]
if temp > res:
temp, res = res, temp
return res
if __name__ == '__main__':
# input
mat = []
for i in range(20):
temp = [int(a) for a in input().strip().split(' ')]
mat.append(temp)
start = time.time()
print('Result : ', MaxMat(mat))
end = time.time()
print('Spent Time : ', end - start)아주 단순하게 구성하였습니다.
- 입력은 한줄씩 string으로 입력받게 되기 때문에, 좌우 공백을 제거하기 위해서 strip( )을 사용합니다. 또한, 공통적으로 한칸씩 떨어져 있기 때문에 split( )으로 잘라주고 이를 List로 반환합니다.
- 중요한 것은 string으로 나뉘기 때문에 int( )로 형변환을 시켜줍니다.
- 입력이 들어오면, 메인 로직이 들어가는 매서드에 해당 값을 전달해줍니다.
- 메인 메서드는... 20 x 20에 대해서 순서대로 순회를 진행하며, 해당 위치에서 방향성에 대해서 4칸씩 연산하여 최대값을 도출합니다.
이때, 중요한 부분은 해당 위치에서 상 / 하 / 좌 / 우 / 대각선 4가지 방향... 총 8가지를 모두 구하지 않는 이유는 이미 기존 단계에서 계산되어 나온 값이기 때문입니다. 세부 코드는 크게 어렵지 않고 더 나은 방법도 많을 것이라 생각하여 생략하겠습니다.
[결과]
Result : 70600674
Spent Time : 0.00599980354306ms에 결과가 도출되었으며, 정확한 값이 나왔습니다~!!
- Ayotera Lab -
댓글