2921 도미노

크기가 n인 도미노세트에 찍힌 점의 총 갯수를 구하는 문제이다.
이 문제는 케이스를 살펴보면 공식을 유추할 수 있다.
n    답
0 -  0
1 -  3
2 -  12
3 -  30
4 -  60

여기서 크기가 n 인 도미노의 점은 n-1 일때의 점의 갯수를 포함하기 때문에  점화식의 형태를 떠올릴 수 있다.
f(n) = f(n-1) + ~

이식에 2를 대입해보면
f(2) = f(1) + 9 = 12

이 된다. 이 9의 값은 어떻게 나왔는지를 유추해보자.

f(1)에서 이미 점이 1개만 찍힌 경우가 나왔으므로 나머지는 한쪽에 점이 2개 찍힌경우이다.
즉, (2,0), (2,1), (2,2) 의 돌이 남게된다.
이것들을 나눠서 계산해보면
2 * 3 + (0+1+2) = 9 가 된다.

이제 f(n) 으로 생각해보면
f(n) = f(n-1) + n*(n+1) + n*(n+1)/2 = f(n-1) + n*(n+1)*3/2
의 점화식이 완성된다.

따라서 f(1)부터시작해서 쌓아 올라가면 f(n)을 구할 수 있다.

물론 이 점화식을 f(n) = ~ 꼴로 바꿀 수 도 있다.
이걸 구하는 공식은 잊어버렸으나(..)
대충 테스트하니까 다음과 같은 공식임을 발견했다.
f(n) = n*(n+1)*(n+2)/2

역시 수학은 잘하고 봐야한다..

소스