오일러 프로젝트 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부터 시작해서 2, 3, 4…를 따라가보면서 빨간색으로 표시된 숫자들을 만날 때의 규칙을 찾아보자.
- 처음 네 개의 값, 1, 3, 5, 7을 만날 때까지는 2씩 증가한다.
- 다음 네 개의 값을 만날 때까지는 4씩 증가한다.
- 그 다음 네 개의 값을 만날 때는 어떨까? 6씩 증가할 것이다. 왜냐하면 방금 휘감은 사각형보다 상하좌우 한 칸씩 늘어난 사각형을 따라 돌기 때문이다.
따라서 증감값은 계속 2씩 커지면서 4번씩 시행한다. 이를 시각적으로 떠올려보면 가운데에서 출발해서 소용돌이를 돌면서 계속 돌아나오는 모양이 된다. 따라서 현재 그려지는 영역의 한 변의 크기 – 1 씩 증가한다. 그러면 끝나는 지점은 어디일까? 증감값이 1000을 넘어서는 시점이되면 끝나면 된다. (혹은 500바퀴를 돈다고 생각하면 된다.) 아래 파이썬 풀이는 500바퀴를 도는 것을 계산했다.
def e028():
a, s, k = 1, 1, 2
for _ in range(1, 501):
for _ in range(4):
a += k
s += a
k += 2
print(s)
%time e028()
# 669171001
# Wall time: 1e+03 µs보너스 : Swift 풀이
Swift에서는 가장 마지막에 돌게될 사각형의 루트는 간격이 1000이 될 것을 이용해서 끊었다.
main: do {
var (s, n, step) = (1, 1, 2)
while step <= 1000 {
for _ in 0...4 {
n += step
s += n
}
step += 2
}
print(s)
}