[백준] 30160. 제곱 가중치

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

문제 요약

• 수열이 주어짐(N:10만, -1000<=숫자<=1000)
• 1, (4,1), (9,4,1), (16,9,4,1), ... 을 곱하고 더한 숫자들을 각각 출력
  • ${1*a_1}$
  • ${4*a_1+1*a_2}$
  • ${9*a_1+4*a_2+1*a_3}$

접근법

• 물론 일일이 구하면 시간 초과
• 인접항의 차이를 구해본다.
  • (2항-1항) : (3,1)
  • (3항-2항) : (5,3,1)
  • (4항-3항) : (7,5,3,1)
• 차이의 차이를 구해본다
  • (2,2,1)
  • (2,2,2,1)
  • ...
• 차이의 차이를 이용해서 인접항의 차이를 구함
• 인접항의 차이를 이용해서 다음 항을 구함