빠똥빠똥
2225번 합분해(DP) - ☆ 본문
#문제링크 : https://www.acmicpc.net/problem/2225
<전략>
1. K개의 합 (ㅁ+ㅁ+ㅁ+...+i) = N 이라고 할때, K-1개의 합 (ㅁ+ㅁ+ㅁ...+ㅁ) = N - i이고, i가 0<= i <= n 의 범위이므로d[n][k]를 n을 k개의 정수의 합으로 나타낸 경우의 수라 하면, d[n][k] = d[n-0][k-1] + d[n-1][k-1] + ... + d[n-n][k-1] 으로 나타낼 수 있다.
※주의사항
1. d[0][0]는 이론상 존재하지 않는 경우지만, 해당 메모이제이션을 위해서는 d[0][0]가 최하단에서 호출되므로, 1로 초기화 해준다.
'백준' 카테고리의 다른 글
| 1904번 01타일(DP) (0) | 2020.07.07 |
|---|---|
| 2011번 암호코드(DP) - ☆ (0) | 2020.07.07 |
| 9461번 파도반 수열(DP) (0) | 2020.06.24 |
| 2133번 타일채우기(DP) - ☆ (0) | 2020.06.24 |
| 1699번 제곱수의 합(DP) - ☆ (0) | 2020.06.23 |
'백준' Related Articles
more
