[C++] 백준2293 - 동전 1

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

2293번: 동전 1

BFS + DFS만 주구장창 하던 나 반성해..

DP 연습 좀 해야겠다고 느낀 문제 😂

그냥 피보나치 수열처럼 단순히 누적으로 넣는 것이 아니라 좀 문제를 제대로 이해해야 전략을 세울 수 있다.

 

문제에서 주어진 예제

동전 3개로 10을 만들어야 한다.

일단 주의할 점은 0원을 만들기 위해서 모두 선택하지 않는 경우의 수 1개가 있다.

 

설명은 아래 그림 참조 (잘 그린지는 모르겠지만.)

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int n, k;
	cin >> n >> k;

	vector<int> arr(n);
	vector<int> dp(k + 1);

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	// 0원 -> 아무 동전도 선택하는 경우 1가지
	dp[0] = 1;

	for (int i = 0; i < n; i++) {
		// 각 동전마다 진행
		// 동전의 값 미만은 경우의 수 0

		for (int j = arr[i]; j <= k; j++) {
			// j=7이고 arr[i] = 2 이면, 2 1개고정에 나머지 5를 만들 수 있는 경우의 수를 더해줌
			// 그게 2 x 3개 + 1 x 1개 이던, 2 x 1개 + 5 x 1개 이든, 앞에 모든 경우의 수가 나타남
			dp[j] += dp[j - arr[i]];
		}
	}
	cout << dp[k];
}