CSES 1. Two Knights (1072)

출처: https://cses.fi/problemset/task/1072

---

문제 설명

Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

입력 

The only input line contains an integer n.

출력

Print n integers: the results.

입력 예

8

출력 예

0
6
28
96
252
550
1056
1848

제약조건

1 <= n <= 10000

---

문제 풀이 

N x N 체스보드에 두개의 knight를 올려 놓는 방법의 경우의 수는 첫번째 나이트를 놓을 수 있는 경우의 수(NxN)와 두번째 나이트를 올려 놓을 수 있는 경우의 수 (NxN-1)를 곱한 만큼이다. 이 중에서 두개의 knight가 서로 공격할 수 있는 경우는 3x2 혹은 2x3의 작은 보드의 마주보는 귀퉁이에 나이트들이 위치하는 경우이다. 이 작은 보드의 수는 2x3의 경우는 (N-1)(N-2), 3x2의 경우는 (N-2)(N-1) 이다. 4개의 귀퉁이가 있으므로 4[(N-2)(N-1)+(N-1)(N-2)]를 전체에서 제외하면 된다. 문제에서는 2개의 Knight 색깔을 구분하지 않으므로, 계산한 경우의 수/2를 하면 답이다.

W
		B

혹은 

W
	B

프로그램 내용

#define MAX_N 10000

int main()
{

    for (long i=1;i<= N;i++)
        unsigned long long k_case;
        k_case = i*i*i*i - 9*i*i + 24*i -16;

        if (i==1)
            cout << 0 << endl;
        else
            cout << k_case/2 << endl;

 

Introductory problems ( link )