https://www.acmicpc.net/problem/2225
이 문제는 2차원 dp로 간단하게 해결할 수 있습니다.
dp[sum][수를 쓴 수]라고 정의를 했습니다.
저는 dfs를 이용해서 메모이제이션했는데요
만약 sum이 N을 초과하면 0을 리턴합니다 더 들어갈 필요도 없기 때문입니다.
만약 해당 깊이(수를 쓴 수와 같음)가 되었는데 내가 원하는 N이 아니라면 0을 리턴하고 맞으면 1을 리턴합니다.
코드입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <string.h> using namespace std; #define ll long long #define MOD (int)1e9 #define MAX_SIZE (int)1e5 #define mp make_pair #define INF 987654321 #define pii pair<int, int> //ios::sync_with_stdio(false); cin.tie(0); int dp[201][201]; int n, k; int f(int sum, int d) { if (sum > n) return 0; if (d == k) { if (sum == n) return 1; else return 0; } int &ret = dp[sum][d]; if (ret != -1) return ret; ret = 0; for (int i = 0; i <= n; i++) { ret += f(sum + i, d + 1); ret %= MOD; } return ret; } int main() { cin >> n >> k; memset(dp, -1, sizeof(dp)); cout << f(0, 0); return 0; } | cs |
'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글
[12026] BOJ 거리 (0) | 2017.07.24 |
---|---|
[1563] 개근상 (0) | 2017.07.24 |
[2158] 동전 교환 (0) | 2017.07.09 |
[1102] 발전소 (0) | 2017.07.08 |
[2698] 인접한 비트의 개수 (0) | 2017.07.04 |