[BOJ 2293] 동전 1

문제

https://www.acmicpc.net/problem/2293

역시 dp는 어렵다 ㅠㅠ 

개인적으로 표를 그리면서 차근차근 푸는것을 추천한다.

예제와 같이 1,2,5원 동전이 있고 10원을 만든다고 가정하면

1원 = 1

2원 = 1+1

   2

3원 = 1+1+1

   2+1

4원 = 1+1+1+1

   2+1+1

   2+2

5원 = 1+1+1+1+1

   1+1+1+2

   1+2+2

   5

이것은 풀어쓰면 dp[5]를 구하는 방법은 dp[1]+dp[2]+dp[0] 인 것을 알 수 있다.

dp[i]라고 가정하면 [i-동전]을 더해주는 방식이다. 처음에 이해가 되지 않아 표를 3번 이상 그려보면서 이해한 문제

시간이 지나면 또 까먹을 듯 하다.

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <functional> #define MAX_SIZE 100 #define INF 0x7fffffff using namespace std; int N, K; int coin[MAX_SIZE]; int dp[10001]; void solve() { dp[0] = 1; scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) scanf("%d", &coin[i]); for (int i = 0; i < N; i++) { for (int j = coin[i]; j <= K; j++) { if (j - coin[i] >= 0) dp[j] += dp[j - coin[i]]; } } printf("%d\n", dp[K]); } int main(void) { solve(); return 0; }