오일러 프로젝트 28

오일러 프로젝트 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. 처음 네 개의 값, 1, 3, 5, 7을 만날 때까지는 2씩 증가한다.
  2. 다음 네 개의 값을 만날 때까지는 4씩 증가한다.
  3. 그 다음 네 개의 값을 만날 때는 어떨까? 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)
}