책 이야기

0~9 사이의 숫자 d로 채워지는 4x4 크기의 격자가 있다.

그 격자는 위와 같이 나타낼 수 있으며, 예시에서 각 열과 행의 합은 12이고, 대각선의 합 또한 12이다.

0~9 사이의 숫자 d로 구성되는 4x4  격자에서 각 행, 열, 두 대각선의 합계가 동일한 경우는 몇가지가 있는가?

--------------------------------------------------------------------------

처음에는 기계적으로 중복순열을 만들어서 해결하려 했으나, 10¹⁶크기의 중복순열을 만들면서 메모리 에러가 발생했다.

그래서 격자의 (0,0)에서 (4,4)까지 a부터 p까지 자리기호를 매기고, (16차) 반복문으로 생성되는 숫자를 기준으로 첫 행의 가로 합계(sum=a+b+c+d)가 나머지 가로 합계(e+f+g+h, i+j+k+l, m+n+o+p), 세로 합계(a+e+i+m, b+f+j+n, c+g+k+o, d+h+l+p), 대각선(a+f+k+p, d+g+j+m)과 동일한 지 확인하도록 구성을 했는데, 10¹⁶ 크기만큼 반복을 하면서 시간이 대책없이 오래 걸리는 문제가 발생했다.

그래서, 고민을 하다 다른 사람이 해결한 방법을 검색해 봤는데, 변수 갯수를 줄이는 형태로 접근해서 실행시간을 개선하는 방법을 제시한 것이 있어 그 방법을 적용해 봤다. 앞 문단에서 설명한 것과 마찬가지 상황에서 sum=a+b+c+d로 했을 때,  가로 세로 합계 공식을 바꿔, h=sum-e-f-g, l=sum-i-j-k, p=sum-m-n-o, m=sum-a-e-i, n=sum-b-f-j, o=sum-c-g-k를 구할 수 있고, 대각선 공식을 이용하면 j=sum-d-g-m이 된다.

a, b, c, d, e, f, g, i, k에 대해 반복문을 구성하여, h, o는 반복문의 값으로 구하고, m을 먼저 구해서 j를 구하고, 그 값을 이용해서 l, p, n를 구할 수 있다. 대각선의 합계가 맞는지 확인하고(sum=a+f+k+p), 연산에 의해 구해진 값(h,j,l,m,n,o,p)이 0~9 사이의 값인 경우에 문제의 조건을 만족하는 경우가 된다.

이것을 반복문을 활용해서 계속 구해나가면 복잡도가 10¹⁶에서 10⁹로 1/10⁷이 줄어들어, 이전보다는 훨씬 빠르지만 그래도 답을 구하는 데는 시간이 좀 필요했다. 다만, 스스로 생각해서 끌까지 해결하지 못하고 다른 사람의 아이디어를 봐야 해결가능하다는 것이 씁쓸했다.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

2x2 격자의 왼쪽 위에서 출발하고, 오른쪽과 아래쪽으로만 이동할 수 있으면, 오른쪽 아래로 이동하는 데에는 정확히 6개의 경로만 있다.
20x20 격자에는 몇 개의 경로가 있는가?
--------------------------------------------------------------------------

격자를 만들고, 이동하는 형태로 반복문을 작성하면 해결 가능할 것 같았는데, 이상하게도 반복문이 만들어지지 않으면서 혼자 논리가 꼬이는 일이 계속되어 답을 구하는 데 많은 시간이 걸렸다. 그래도 아직 답을 구하는 규칙을 찾지 못한 26번에 비하면 빨리 답을 구한 편이긴 하다.

15번이면 비교적 앞쪽의 문제인데 해결방안을 못찾아 애먹으면서 답답했지만, 한 번 논리가 꼬여버린 논리를 푸는 것은 어려운 일이라는 것을 다시 한 번 느꼈고, 좋은 논리로 해결하지 못하고 단순하게 해결할 수 밖에 없어 답답했던 문제이다.

divide and conquer라는 분할정복 방법으로 접근할 수 밖에 없었고, 1x1에서는 2개, 2x2에서는 6개, 3x3에서는 20개로 늘어나는 과정을 쪼개어서(3x3 경로를 1x1, 2x2의 경로를 이용해 구하기) 이전 과정의 합계를 활용하는 규칙을 찾아 그것을 프로그램으로 해결하였다.

이제 생각해보니 전체 2n개의 경로에 n개의 한 방향을 입력하면 되는 것이어서 조합을 이용하면 간단히 답을 구할 수 있는 것이었다.

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?

20x20 격자에서 대각선으로 연속된 4개 숫자는 굵게 표시되어 있다.

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

네 숫자의 곱은 26x63x78x14=1788696이다.

20x20 격자에서 같은 방향으로(위쪽, 아래쪽, 왼쪽, 오른쪽, 대각선) 연속된 4개 숫자의 곱이 가장 큰 것은 얼마인가?

--------------------------------------------------------------------------

파이썬 자료형 처리에 익숙하지 않아서, 이 문제도 문제해결 보다는 자료형을 어떻게 처리하는 것이 효율적인지 고민하는 데 더 많은 시간이 들었던 문제이다. 위 격자를 읽어서 20x20 크기의 2중 리스트를 생성하기로 결정하고, 문제 자체는 반복문을 이용하여 곱이 가장 큰 경우를 구하면 되기 때문에 어렵지 않게 해결할 수 있었다.

연속된 4개의 숫자를 곱하기 때문에, 첫 줄을 가로로 곱하는 경우 17번을 하면 끝까지 확인할 수 있는 것처럼 각 방법별 반복횟수를 조금 신경써주면 된다. 각 방법별 시작, 끝 위치가 달라 가로, 세로, 왼쪽 대각선, 오른쪽 대각선의 4가지 반복구조를 구성해서 구하였다.