C++ - 백준 2921 도미노

/* 백준 2921 도미노
https://www.acmicpc.net/problem/2921

* 문제

도미노는 여러 종류의 타일 게임에서 사용하는 조각이다. 도미노 조각은 두 칸으로 이루어져 있다.
각 칸에는 점이 찍혀있는데, 점이 안 찍혀져 있을 수도 있다. 점의 개수는 세트의 크기에 의해서
결정된다. 세트의 크기가 N인 도미노 세트에서 점의 개수는 0보다 크거나 같고, N보다 작거나
같다. 두 도미노에 찍혀잇는 점의 개수가 같다면, 두 도미노는 동일한 것이다. 예를 들어, 점이
2개와 8개 찍혀있는 도미노는 8개와 2개 찍혀있는 도미노와 같은 도미노이다.

크기가 N인 도미노 세트는 N 또는 그보다 작거나 같은 점을 포함하는 가능한 도미노를 모두
포함하고 있고, 각 도미노는 중복되지 않는다. 다음은 크기가 2인 도미노 세트이다.

    점의 개수    0   0   1   0   1   2
                0   1   1   2   2   2

N을 입력받은 뒤, 크기가 N인 도미노 세트에는 점이 몇 개 찍혀 있는지 구하는 프로그램을 작성하시오.

* 입력

첫째 줄에 도미노 세트의 크기 N (1 ≤ N ≤ 1000)이 주어진다.

* 출력

크기가 N인 도미노 세트에 찍혀 있는 점의 개수를 출력한다.

* 예제 입력 1

2

* 예제 출력 1

12

* 예제 입력 2

3

* 예제 출력 2

30

* 예제 입력 3

15

* 예제 출력 3

2040

* 풀이

1)

    2 dominos   top     0           top 이 0일 경우 bottom 은 0, 1, 2
                bottom  0   1   2

                top     1           top 이 1일 경우 bottom 은 1, 2 (0은 중복)
                bottom  1   2

                top     2           top 이 2 일 경우 bottom 은 2 (0, 1 은 중복)
                bottom  2

    모든 점의 개수를 더하면 (0 + 0) + (0 + 1) + (0 + 2) + (1 + 1) + (1 + 2) + (2 + 2)
    가 된다.

    3 dominos   0   0   0   0   1   1   1   2   2   3
                0   1   2   3   1   2   3   2   3   3

    이것을 구현하는 것은 간단하다.

2)

    근데, 조금 더 최적화가 가능할 것 같다.

    2 dominos   0   0   1   0   1   2           : 합이 4
                0   1   1   2   2   2           : 합이 8

    3 dominos   0   0   0   0   1   1   1   2   2   3       : 합이 10
                0   1   2   3   1   2   3   2   3   3       : 합이 20

    ==> 위쪽 합에 x 3 하면 되지 않을까? ==> 된다.

3)

    최적화의 길은 끝이 없고... 뭔가 좀 더 간단한 규칙이 있을 것 같다.
    근데, 이거 푼다고 밤 샌거 같네. 그냥 1), 2) 풀이로 풀자.

    1. 도미노는 두 칸으로 이루어져 있고 각 칸에는 0~n 개의 점이 찍혀 있다.
    2. 이거 대충 계산해 보면 2 칸 각각에 (n + 1) 개의 경우가 있으므로, (0 ~ n 까지)
       전체 (n + 1)^2 의 경우의 수가 있다.
    3. 이제, 이 중에서 중복 되는 경우를 전부 빼는 작업을 해 보자.
       각 칸의 점의 개수가 같을 경우 칸의 위치가 달라도 같은 도미노로 판정되므로,
       ([1, 2] 와 [2, 1] 은 같은 도미노)

       [a, b] 에서 a == b 일 경우에는 일단 unique 하다고 판정하고 count 한다
                  a != b 일 경우 [a, b] 와 [b, a] 는 같은 값으로 count 한다

        ==> 조금 생각해 보면 도미노는 두 칸만 존재하므로, [a, b], [b, a] 경우 밖에 없다.

    4. 이것을 정리하면, 전체 경우 중에 [a, b] 에서 a == b 일 경우와 a != b 일 경우의 점의
       개수를 모두 구해서 더하면 될 것이라는 것을 알 수 있다.

    5. 이제, 이 문제를 풀기 위해 조금 고민해 보자.

       1)  a == b 인 경우 숫자의 합은

           2(0 + 1 + 2 + ... + n) = 2 x n(n+1)/2 = n(n + 1)      ... (1)

           이 된다.

           여기까지는 쉽다.

       2) a != b 인 경우
          (a, b 가 0 일 때는 어차피 더해도 0 이므로 다음에 나오는 ∑ 식에는 0 부터로 적는다.)

            n-1 n
            ∑   ∑    (a + b)
            a=0 b=a+1

            가 된다. (a != b 이므로...)

       그러므로, 최종 답은 1) 의 답 + 2) 의 답이 될 것이다.
       1) 의 답은 간단히 이미 풀었기 때문에 2) 의 답을 조금만 풀어 보자

            n-1 n                  n-1   n       n
            ∑   ∑    (a + b)  =    ∑   ( ∑  a + ∑  b)
            a=0 b=a+1              a=0   b=a+1   b=a+1

        여기서,

            n
            ∑  a   = (n - a) * a  이므로,
            b=a+1

            n-1 n                  n-1   n       n          n-1                n
            ∑   ∑    (a + b)  =    ∑   ( ∑  a + ∑  b)   =   ∑   ((n - a) * a + ∑  b)
            a=0 b=a+1              a=0   b=a+1   b=a+1      a=0                b=a+1

            이다.

            여기서, 안쪽에 있는

            n        n      a
            ∑  b   = ∑  b - ∑  b  이므로,
            b=a+1    b=0    b=0

            n(n + 1) / 2  + a(a + 1) / 2 와 같다.

            이제, 이것을 정리하면,

            n-1                n
            ∑   (n - a) * a +  ∑  (n(n + 1)/2 - a(a + 1)/2)
            a=0                a=0

            와 같이 된다. 이것을 풀라면 텍스트모드로 도저히 적기가 힘들기 때문에 결론만
            적으면,

            n                   n
            ∑   k = n(n+1)/2,   ∑   k^2 = n(n+1)(2n+1)/6
            k=0                 k=0

            을 적당히 사용하면,

            (n-1)n(n+1)/6 + ( n(n+1)n/2 - (n-1)n(n+1)/6 )           ... (2)

            이 된다.

            이제, (1) 과 (2) 를 더해서 식을 정리하면,

            n x (n + 1) x (3n + 6)       n x (n + 1) x (n + 2)
            ----------------------   =   ---------------------
                        6                          2

            가 된다.

            이것이 O(1) 의 시간복잡도를 가지기 때문에 가장 좋은 답이라고 할 수 있지만...
            이해하려면 조금 머리가 아플 것이다.
*/

#include <iostream>

int main() {
	// std::cin.tie(nullptr)->sync_with_stdio(false);

	int n;
	std::cin >> n;

	// 풀이 1)

	// int count = 0;
	// for (int i = 0; i <= n; ++i) {
	// 	for (int j = i; j <= n; ++j) {
	// 		count += i + j;
	// 	}
	// }
	// std::cout << count << '\n';

	// 풀이 2)

	// int count = 0;
	// for (int i = 1; i <= n; ++i) {
	// 	for (int j = 1; j <= i; ++j) {
	// 		count += j;
	// 	}
	// }
	// std::cout << count * 3 << '\n';

	// 풀이 3)

	std::cout << n * (n + 1) * (n + 2) / 2 << '\n';
}