책 이야기

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⁷이 줄어들어, 이전보다는 훨씬 빠르지만 그래도 답을 구하는 데는 시간이 좀 필요했다. 다만, 스스로 생각해서 끌까지 해결하지 못하고 다른 사람의 아이디어를 봐야 해결가능하다는 것이 씁쓸했다.

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

주의: 이 문제는 문제81 보다 더 어렵다.

첫번째 열의 원소에서 시작해서 마지막 열에서 끝나며 위, 아래, 오른쪽으로만 움직일 때 아래의 5x5 행렬에서 최소 경로는 붉은 색으로 굵게 표시되어 있으며 합계는 994이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭 하고 "다른 이름으로 링크 저장")의 첫번째 열에서 마지막 열까지 이동할 때 최소 경로의 합계를 구하시오.

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

81번 문제를 해결한 방법을 그대로 사용할 수는 없었지만, 그 방법을 가져와서 반복을 통해 해결했다. 81번 문제에서는 답을 구할 자리가 행렬 전체의 마지막 자리(80, 80)이지만, 이번 문제에서는 마지막 열(x,80) 모두가 답이 되는 후보이기 때문에 마지막 열 각 행을 기준으로 최소 경로의 값을 구하는 방식으로 접근했다..

위 예시를 기준으로 예를 들면, 2번째 열, 2번째 행의 최소값 후보는 1번째 열 각 행에서 시작한 5개 경로의 값 900(131+673+96), 297(201+96), 1529(630+803+96), 2135(537+699+83+96), 3135(805+732+699+803+96) 중 가장 작은 297이 된다. 이 예시에서 131다음에 201로는 왜 안가고 673으로만 가는지 의문이 들 수 있는데, 이 경우 201에서 시작한 경우보다는 무조건 크기 때문에 최소값이 될 수 없다고 생각해서 배제했다.

이런 식으로 각 열의 최소값을 2번째 열부터 마지막 열까지 구하고, 마지막 열 각 행의 최소 경로 값 중에서 제일 작은 값을 찾으면 된다. 그런데, 다중 반복문을 실행하느라 시간이 7초 이상 걸리는 것을 보면 좀 더 빠른 방식으로 해결하는 방법이 있을 것 같다.