목록합분해 C++ (1)

1일1알

백준 2225번 합분해 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. dp테이블을 dp[n][k]라고 하고, k개의 수로 n을 만들 수 있는 경우의 수 라고 하였다. 의외로 간단하게 해결할 수 있다. 예를 들어 dp[3][4]는 4개의 수로 3을 만들 수 있는 경우의 수인데, 마지막에 0이 온다면 3개의 수로 3를 만드는 경우의 수, 마지막에 1이 온다면 3개의 수로 2을 만드는 경우의 수, 마지막에 2가 온다면 3개의 수로 1를 만드는 경우의 수, 마지막에 3이 온다면 3개의 수로 0을 만드는 경우의 수 이다. 이 경우들을 모두 합하면 되기 때문에 점화식은 dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + dp[n-2][k-1] + .... dp[0][k-1] 이다. 그리고 테이블을 채워가다 보면 dp..
알고리즘 2022. 1. 2. 12:24
이전 Prev 1 Next 다음