28. 프로젝트 오일러 #28 : 회전하는 숫자들의 대각선 합

이 프로그램은 사실 원하는 배열을 잡고, 숫자를 배열한 후에 대각선의 합을 구해도 됩니다.

그렇게 한다고 해서 시간이 엄청 걸리는 것도 아니니 말이죠.

그러나 처음 제가 이 프로젝트 오일러 글들을 쓰면서, 어떻게 하면 보다 빠르게 계산할 것인가를 고민했기 때문에, 이 문제 역시 복잡도를 낮추어 계산하도록 하였습니다.

1부터 N까지의 합, 제곱 합 등의 공식을 도출할 줄 안다면, 이 문제 역시 간단하게 하나의 식으로 만들 수 있습니다.

여기서는 다음과 같은 식이 나오게 됩니다.

이 수식에 따라서 구한 프로그램은 다음과 같습니다.

역시 이 프로그램은 참고용으로만 해주세요.

#include <stdio.h>

int main()
{
    int n;

    scanf("%d", &n);

    n = (n-1)/2;

    printf("Ans = %d\n", 1+8*n*(n+1)*(2*n+1)/3+2*n*(n+1)+4*n);
}