[BeakJoon 2293] 동전 1

안녕하세요. 이번 포스팅에서는 저번 포스팅에 이어 동전 1을 풀어보도록 하겠습니다.

(저번 포스팅)

https://chanho0912.tistory.com/78?category=870985 

[BeakJoon 2204] 동전 2

 

이번에 풀어 볼 문제는 

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

2293번: 동전 1

위 링크에서 확인하실 수 있습니다.

 

 

저번에는 만들 수 있는 동전의 조합 중 최소의 개수를 사용하는 방법을 묻는 문제였다면, 이번에는 모든 경우의 수를 묻는 문제입니다.

 

초기값 dp[0] = 1로 설정해 주시고, 

저번과 같은 순서로 탐색을 진행하며, 이번에는 만들 수 있는 모든 경우의 수를 구하는 경우이므로 모두 더해주시면 됩니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int n, k, dp[100004];
vector<int> v;
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		v.push_back(a);
	}
	
	dp[0]=1;
	for(auto coin : v) {
		for(int j = 0; j <= k; j++) {
			if(j-coin >= 0) dp[j] += dp[j-coin];
		}
	}
	cout << dp[k];
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.