[BAEKJOON] 2293번 : 동전 1

문 제

 

소 스  코 드

#include <iostream>

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, K;

	std::cin >> N >> K;

	int *coins	{ new int[N] };
	int *dp		{ new int[K + 1] };
	for (int i = 0; i < N; ++i) std::cin >> coins[i];
	std::fill_n(dp, K + 1, 0);
	dp[0] = 1;

	for (int i = N - 1; i >= 0; --i) {
		for (int j = 0; j <= K; ++j) {
			if (coins[i] <= j) {
				dp[j] += dp[j - coins[i]];
			}
		}
	}

	std::cout << dp[K] << '\n';

	delete[] dp;
	delete[] coins;
	return 0;
}   

 

풀 이

 

먼저, N가지 종류의 동전을 가지고, K원이 되도록 하는 문제이다.

DP를 사용하여 하는 문제인데, 

DP[j] j는 가치의 합이다.

 

만약, 5의 동전을 가지고 1원을 만드는 방법은 dp[1] = 0 이다.

 

이런식으로,

 이런 그래프를 통해서 구현이 가능하다.

 

5의 동전을 가지고, 5와 10의 가치합 dp[5], dp[10] 을 1로 만들 수 있다.

이렇듯, 이와 같이 dp[ j ] + dp[ j - arr[n] ] 을 통한다면, 경우의 수를 구 할 수 있다.

 

 

 

순서가 바뀌어도 문제 없이 동작하는 것을 알 수 있다.

 

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/2293

2293번: 동전 1