★ solved.ac 난이도 : B3
(작성 시점 기준)
[문제 본문 링크]
2721번: 삼각수의 합
n번째 삼각수, T(n)은 1부터 n까지의 합이다. T(n) = 1 + ... + n. 이것은 삼각형 모양으로 표현할 수 있다. 아래 그림은 T(4)를 나타낸 것이다. 다음과 같은 식을 통해 가중치를 부여한 삼각수의 합을 구
www.acmicpc.net
★ 풀이
먼저 아래와 같은 함수를 정의합니다.
- T(n) = 1부터 n까지의 합 = n(n+1)/2
- F(k) = k×T(k+1) = k(k+1)(k+2)/2
- W(n) = Sum[k=1..n; F(k)]
사용하는 등식은 다음과 같습니다.
- Sum[k=1..n; n2] = n(n+1)(2n+1)/6
- Sum[k=1..n; n3] = {n(n+1)/2}2
여기에서 F(k)를 전개하면 (k3+3k2+2k)/2가 됩니다.
그리고 위에 있는 등식을 적용하면
- Sum[k=1..n; (k3+3k2+2k)/2]
- = [{n(n+1)/2}2 + 3{n(n+1)(2n+1)/6} + n(n+1)]/2
- = (n4 + 2n3 + n2)/8 + (2n3 + 3n2 + n)/4 + (n2 + n)/2
- = (n4 + 6n3 + 11n2 + 6n)/8
- = n(n+1)(n+2)(n+3)/8
따라서 n(n+1)(n+2)(n+3)/8의 값을 출력하면 됩니다.
[소스 코드]
★ 틀린 점이 있다면 알려주세요~!