오일러 프로젝트 28

숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.

        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

여기서 대각선상의 숫자를 모두 더한 값은 101 입니다. 같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까?

http://euler.synap.co.kr/prob_detail.php?id=28

접근

위 문제의 표에서 1부터 시작해서 나선 모양으로 숫자들을 지나가면서 몇 개마다 빨간 숫자를 만나는지 세어보자.

1. 3, 5, 7, 9, 이렇게 4개의 값은 2씩 증가할 때마다 만나게 된다.
2. 다음 바깥쪽에 있는 13, 17, 21, 25는 4씩 증가한다.
3. 그림에는 없지만 그 다음 번 외곽의 4개는 6씩 증가한다. 이렇게 4개의 숫자를 만난 후에는 각 변이 2씩 늘어난 정사각형의 주위를 돌기 때문에 step에 해당하는 값이 2씩 커지게 된다.
4. 이 step의 값이 1000이 되면 가장 외곽을 순회한 셈이된다.

이상의 과정을 그대로 코드로 옮겨서 계산하면 된다. 순식간에 계산된다. 이렇게 쉬운데 왜 28번인지 모르겠네.

s, n, step = 1, 1, 2
while step <= 1000:
  for _ in range(4):
    n += step
    s += n
  step += 2
print(s)