원문 : Largest product in a grid.



In the 20x20 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 number is 26 x 63 x 78 x 14 = 1788696.


What is the greatest product of four adjacent numbers in the same direction( up, down, left, right, or diagonally ) in the 20x20 grid?


아래의 20x20 그리드에서, 대각선을 따라 존재하는 네 개의 숫자가 붉은 색으로 표시되어 있습니다.


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 x 63 x 78 x 14 = 1788696 입니다.


20x20 그리드의 같은 방향( 위쪽, 아래쪽, 왼쪽, 오른쪽, 대각선 )에 있는 4 개의 인접한 숫자들의 곱 중에서 가장 큰 숫자는 무엇일까요?


Brute-Force


이 문제를 가시화하면 다음과 같습니다. ( i, j ) 요소를 중심으로 살펴 보시다. 그러면 아래 그림에서 검은색을 중심으로 색칠해져 있는 부분들의 곱을 구해서 가장 큰 숫자들을 찾으면 됩니다.



그런데 딱 봐도 루프를 돌 때 중복되는 부분이 많을 것 같다는 생각이 듭니다. 특정 방향은 다른 좌표를 중심으로 하는 셸을 계산할 때 서로 겹치므로 배제될 수 있습니다( 예를 들어 왼쪽과 오른쪽, 위쪽과 아래쪽, 위쪽 대각선과 아래쪽 대각선 ).



이 정도로 최적화라고 부르긴 좀 뭐해서 여기까지 Brute-Force 라 생각하도록 하겠습니다.



답은 70600674 입니다.


Other's solution


다른 사람들의 구현을 살펴 봤는데, 루프를 도는 방식에 조금 차이가 있을 뿐이고 크게 다르지는 않더군요.


그런데 파이썬에서 동적으로 자료구조를 만드는 편리한( 코드가 짧은 ) 방법들이 있는데, 꽤 어렵네요. [ JASON'S CODE BLOG ] 에서는 다음과 같이 2 차 배열을 만듭니다.



파이썬은 문법이 뭔가 살짝 괴랄하지만 익숙해지면 편하게 쓸 수 있을 것 같아 보이네요.

+ Recent posts