숫자 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부터 시작해서 나선 모양으로 숫자들을 지나가면서 몇 개마다 빨간 숫자를 만나는지 세어보자.
- 3, 5, 7, 9, 이렇게 4개의 값은 2씩 증가할 때마다 만나게 된다.
- 다음 바깥쪽에 있는 13, 17, 21, 25는 4씩 증가한다.
- 그림에는 없지만 그 다음 번 외곽의 4개는 6씩 증가한다. 이렇게 4개의 숫자를 만난 후에는 각 변이 2씩 늘어난 정사각형의 주위를 돌기 때문에 step에 해당하는 값이 2씩 커지게 된다.
- 이 step의 값이 1000이 되면 가장 외곽을 순회한 셈이된다.
이상의 과정을 그대로 코드로 옮겨서 계산하면 된다. 순식간에 계산된다. 이렇게 쉬운데 왜 28번인지 모르겠네.
s, n, step = 1, 1, 2
while step <= 1000:
for _ in range(4):
n += step
s += n
step += 2
print(s)