[백준/BOJ] 11560 다항식 게임

문제

출처 : www.acmicpc.net/problem/11560

11560번: 다항식 게임

k에 따라 다항식이 연결된다.

k = 0

(1)

k = 1

(1)(1+x)

k = 2

(1)(1+x)(1+x+x^2)

k = 3

(1)(1+x)(1+x+x^2)(1+x+x^2+x^3)

.

.

.

k = ? 일때의 다항식을 계산한 결과에서 N차항의 계수를 출력하는 문제다.

 

풀이

k = 20 , N = 210까지 간다.

k가 늘어남에따라, 곱해야하는 항의 차수 또한 매우 늘어나므로, 완탐으로 풀경우 시간초과가 난다.

 

DP로 풀었던 문제인데,

 

k = 0

(1)

k = 1

(1)(1+x)

k = 2

(1)(1+x)(1+x+x^2) 

k = 3

(1)(1+x)(1+x+x^2)(1+x+x^2+x^3)

 

를 보면, (당연한)규칙??을 찾을수있다. N차수의 다항식은 자신보다 작은 차수를 가진 다항식의 계수의 합들로 구성된다는것이다.

예를들어,

 

k = 2를 보자. k = 2 를 계산해보면, 1 + 2x + 2x^2 + x^3 이 된다.

이때, x^3의 계수를 결정하는것은 k = 1에서 구해놓은, x^1 * x^2이다. 이때, x^1의 계수는 1이므로, x^3의 계수는 1이된다.

마찬가지로, x^2의 계수를 결정하는것은, k = 1일때 구해놓은, 1 * x^2 과 x^1 * x^1 이된다. 이 두가지를 더하면 계수는 2 가되고, 따라서

k = 3 일때, x^2의 차수는 2 가 된다.

 

따라서, dp[k][차수] = 계수 형태로 저장해줄때,

dp 식은 dp[k][차수] = dp[k][차수] + (전단계 차수가 갖고있는 계수 * 1);

이 된다.

 

풀이

https://github.com/devxb/JJUNalgo/blob/master/11560%20%EB%8B%A4%ED%95%AD%EC%8B%9D%20%EA%B2%8C%EC%9E%84/main.cpp

devxb/JJUNalgo