Daily Algorithm - Day 27

Number Spiral Diagonals

Starting with the number $1$ and moving to the right in a clockwise direction a $5$ by $5$ spiral is formed as follows:
21 22 23 24 25
20  7  8   9  10
19  6  1   2  11
18  5  4   3  12
17 16 15 14 13
It can be verified that the sum of the numbers on the diagonals is $101$.

What is the sum of the numbers on the diagonals in a $1001$ by $1001$ spiral formed in the same way?

위의 나선 행렬과 같은 방식으로 $1001 \times 1001$ 행렬을 만들었을 때 대각선 상의 수를 모두 더한 값을 구하는 문제이다.

나선 행렬을 직접 구현하면서 구하는 방법도 좋겠지만 수학적으로 접근해보자.

먼저 $3 \times 3$ 행렬에서 모서리의 숫자들은 3~9 까지 2씩 늘어난다.
그리고 $5 \times 5$ 행렬에서 모서리의 숫자들은 13~25 까지 4씩 늘어난다.
같은 방식으로 $7 \times 7$ 행렬에서 모서리의 숫자들은 31~49까지 6씩 늘어난다.

즉 $n \times n$ 행렬에서 모서러의 숫자들은 $(n-2) \times (n-2)$ 행렬의 모서리 숫자 중 가장 큰 숫자에서 $(n-1)$을 더한 값 부터 시작해서 $(n-1)$씩 늘어나는 4개의 숫자다.

그리고 가운데 숫자인 $1$과 이 모서리의 숫자들이 바로 대각선 상의 숫자다. 이 점을 이용해서 구현해보자.

# n*n 나선 행렬의 대각선 상의 수를 모두 더해주는 함수
def solution(n):
    diagonals_sum = 1 # 합한 값
    last_number = 1 # 이전 행렬의 마지막 숫자 기록용
    # 3 ~ n까지 홀수만
    for i in range (3, n + 1, 2):
        for j in range(4):
            last_number += i - 1
            diagonals_sum += last_number
                
    return diagonals_sum

print(solution(1001))

>>> 669171001   #correct

그리고 $n \times n$ 행렬의 모서리 값 중 가장 큰 값은 $n^2$이다. 즉 모서리 4개의 값을 구하자면 각각 $n^2, n^2-(n-1),n^2-2(n-1),n^2-3(n-1)$로 이를 모두 더하면 $4n^2-6(n-1)$이 나오므로 이를 이용해도 좋을 것 같다.

def solution(n):	
    diagonals_sum = 1
    for i in range (3, n + 1, 2):
        result+=4*i**2 - 6*(i - 1)
    return diagonals_sum

print(solution(1001))

>>> 669171001   #correct

워낙 간단한 코드이니 gpt 선생님의 리뷰는 넘기도록 하자.
오늘은 여기까지.
-2025.01.17-