[BOJ] 1492번: 합

https://www.acmicpc.net/problem/1492

$1^K + 2^K + 3^K + ... + N^K$를 계산하는 공식은

$(N+1)^{K+1} - N^{K+1}$

$+N^{K+1} - (N-1)^{K+1}$

.

.

.

$+2^{K+1} - 1^{K+1}$

을 합하고 나면 어찌저찌 구해집니다. 전개과정은 귀찮아서 생략..

$D[k] = 1^k + 2^k + ... + N^k$ 라고 두면 $D[K]$를 $D[1]$, .. , $D[k-1]$로부터 계산이 가능해져 DP로 해결할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/1492.cpp