[백준 25974] 거듭제곱의 합1 (python)

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

25974번: 거듭제곱의 합 1

 

거듭제곱의 합1 문제

백준의 1492 합 문제와 동일한데 제곱의 단위수가 20배나 높은 문제.

파스칼의 삼각형 개념과 다이나믹 프로그래밍을 통해서 해결할 수 있었다.

 

📌 문제 접근 포인트

0. 제곱 수들의 합 아이디어에 대해서 참고하면 좋을 사이트

https://www.mathpages.com/home/kmath279/kmath279

아래 내용이 이해가 안되면 위 사이트(특히 C가 나오는 적분 파트)를 먼저 보고 오는 것을 추천

 

1. 제곱 수들의 합을 구할 방법을 생각해보자.

아이디어를 떠올리기 위해서 먼저 k=1일때부터 생각해보자. 일반적으로 k = 1일때의 n까지의 합의 공식에 대해서는 이미 알고있다.

k=2일 때도 알고 있다.

그렇다면 공식으로 k에 대해서 공식을 만들 수 있지 않을까? 라는 생각으로 접근해보자.

합의 공식을 만드는 과정에 대해서 알고 있으면 접근 할 수 있다.

일반항을 만드려고 시도를 해보자. 기본적인 전개식은 아래와 같다

이 식을 이용해서 구해보자. 아래처럼 k+1항에 대해 계산을 할 수 있다.

그러면 오른쪽 최고차항을 우측으로 바꿔보자.

이 식을 n=1부터 대입해서 식을 만들어보자.

...

이제 각각 좌변 우변을 더해주면 제곱의 합에 대해 구할 수 있다.

좌변은 중간 항들은 계산해서 사라지고, 우측 항들은 각각 1~N까지 합한 항들이 된다.

즉, 이 식에 대해서 조금 더 이쁘게 정리해서 보면

다음처럼 식이 정리가 된다. 그렇다면 임시로 아래처럼 정의해주자.

그렇다면 우리가 필요한 이 f(m) 식은 다음처럼 계산된다.

이렇게 만들어낸 식을 이용해서 문제를 풀어보자.

2. 그렇다면 이 식을 어떻게 활용하면 좋을까? 

이항계수를 계산하는 과정에서 필요한 항목은 팩토리얼과 제곱 수를 계산해줄 분할정복 등이 필요하다. 그렇다면 팩토리얼, 이항계수, 분할정복에 대한 함수를 각각 정의해서 사용하게 되는데 이렇게 될 경우, p의 수가 1000까지 되니 연산수가 굉장히 올라가서 시간 초과가 뜰 수 밖에 없는 구조가 된다.

3. 그렇다면 이항계수를 팩토리얼 등을 사용하지 않고 계산할 방법을 생각해보자. 이항 계수를 구하는 방법 중에 '파스칼의 삼각형' 개념을 이용하면 이항계수를 구할 수 있다.

4. 간단하게 파스칼의 삼각형을 구현해주고, 위 식대로 계산해서 연산해주면 굳이 분할 정복, 팩토리얼 등을 활용하지 않아도 다이나믹 프로그래밍을 통한 연산으로 답을 도출 할 수 있었다.

 

✔ 추가 부분

합에서 사용한 코드를 그대로 이 문제에 쓰면 연산 수로 인해 시간초과가 뜬다

⚙ 내가 푼 정답 코드

import sys
N, p = map(int,sys.stdin.readline().split())
mod = 10**9+7
C = [[1]*(p+2) for _ in range(p+2)]
for i in range(1,p+2): # 파스칼의 삼각형을 이용한 이항계수
   for j in range(1,i):
      C[i][j] = C[i-1][j-1] + C[i-1][j]
dp = [0]*(p+1)
dp[0] = N

for i in range(1,p+1):
   x = (N+1)**(i+1) -1 # 누적 합 공식
   for j in range(i): # 누적합에서 이전 꺼 차이를
      x -= C[i+1][j] * dp[j] 
   dp[i] = x // (i+1) # 이항계수로 나눠주기

print(dp[p] % mod) # 결과