#include <cstdio> #include <iostream> using namespace std; int main() { int n, k; int coins[101]; int d[10001] = { 0 }; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> coins[i]; } d[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { if (j >= coins[i]) { d[j] += d[j - coins[i]]; } } } cout << d[k] << endl; return 0; } |
자 보면, 여기서 여러가지 인덱스 처리에 대해서 익숙해지면 됩니다. 디피 문제는 그렇습니다. 재귀같은 느낌이 있긴 한데, 이것을 어렵게 느끼는 것이 아니라, 규칙을 만들고 그에 대해서 풀이를 진행하면 됩니다. 그런데 규칙을 찾기 위해서는 아이디어에 대해서 말로 풀어 쓰기가 가능해야 합니다. [][] 2차 행렬로 풀이를 하는 것에 대해서는 신선하였습니다. |
표를 만들어서 풀이해서 그 점화식을 만들면 좋겠습니다. 그 표를 만들기 위해서는 어떻게 처리 해야하는가요? 그리고 접근할때 1개로 만들 수 있는 경우 2개로 만들 수 있는 경우 3개로 만들 수 있는 경우가 있습니다. 이것들에 대해서 추가를 해야하는 추가하는 것들에 대해서도 알아야하는 가요? 아니면 일단 결론까지만 파악을 하고 그 이후를 파악할 수 있으면 좋겠습니다. |