[Project Euler] 28. 1001×1001 나선모양 행렬에서 대각선 원소의 합은?

28. 1001×1001 나선모양 행렬에서 대각선 원소의 합은?

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

21 22 23 24 25

20 07 08 09 10

19 06 01 02 11

18 05 04 03 12

17 16 15 14 13

여기서 대각선상의 숫자를 모두 더한 값은 101 입니다.

같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까?

Click

일단 푸념하고 시작합니다.
아.... 난 수학을 하는 것인가 프로그래밍을 하는 것인가.......
푸념 끝. 그럼...

nxn 행렬에 대해 대각선 값이
1부터 시작, 2,2,2,2, 그리고 4,4,4,4, ..... (n-1),(n-1),(n-1),(n,1) 씩 더해주며 증가.
우측 상단으로 가는 대각선은 1²,3²,5²......n²으로 증가.
이런 패턴들을 정리하면... k껍데기에 있는 대각선 들의 값은

 k²+ (k²- (k-1)) + (k²- 2(k-1)) + (k² - 3(k-1)) = 4k² - 6k + 6 (k=1 제외)

으로 나타낼 수 있다.
이제 이 껍데기들을 k=3부터 k=n까지 k=k+2씩 더해준 후 마지막에 1만 더해주면 결과가 나온다.
그런데 여기서 한번 더 보면.
k값을 (i=1부터 i=(n-1)/2까지 i++, k = 2*i+1)로 바꿀 수 가 있다. 이를 다시 위에 식에 적용하면.

 4(2*i+1)²- 6(2*i) + 6 = 16*i²+ 4i + 1

이 되고. 이 수들을 더한 값을 시그마(∑)로 나타내면.. ((n-1)/2 = t로 놨을때..)

 (i=1 부터 i = ((n-1)/2) = t 까지) ∑(16*i²+ 4i + 1) = 16∑i²+ 4∑i + 4∑1
                                            = 16*(t*(t+1)*(2t+1)/6) + 4*(t*(t+1)/2)) + 4*t
                                            = (16t³)/3 + 8t²+ (8t)/3 + 2t²+ 2t + 4t
                                            = (16t³)/3 + 10t²+ (26t)/3
                                            = (16t³ + 30t²+ 26t)/3

이제 다시 t를 (n-1)/2로 하면... 뭔가가 나오겠지만 여기서는 귀찮으니 그냥 구현.
마지막에 위에서 제외한 예외의 경우 k=1일때 값 1을 더해주는 것도 잊지 않고!!

사실 그냥 손계산은 여기서 계산하는게 더 쉽습니다.
한단계 더 나간다고 뭐 그렇게 어려운 것은 아니지만... 여기서 n값.. 1001에 -1 후 /2를 하면 500이 나오고... 500을 위에 식에 대입하면 끝....
물론 계산기의 힘을 동원하는게 여러모로 편하지만요....

물론 컴퓨터가 계산하는데는 한단계 더 나간것까지 풀어주는게 더 좋겠지만 그래봐야 아주아주아주아~ 주 극미한 차이이니 pass.
사실 이정도만 해도 코딩 두줄로 끝나니.....

<script language="Javascript" type="text/javascript">
function p028(n){
    var t = (n-1)/2;
    alert((16*t*t*t + 30*t*t + 26*t)/3 + 1);
}
</script>