[BOJ/백준] 2293번 - 동전 1

 

동전 1

 

문제

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

2293번: 동전 1

 

문제 요약

주어진 동전들을 통해 목표합을 만드는 경우의 수를 구한다.

• 동전의 중복 사용을 허용
• 중요! 동전 순서가 다르면, 같은 경우로 인정

 

!! 아래 문제와 유사해 보이지만, 조건이 다르다.

https://salon.tistory.com/60?category=1191940

[Dynamic progamming] Coin Combinations I

 

CODE

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

const int mxN=100, mxK=1e5; 
int n, k, c[mxN+1];
int dp[mxK+1];

int main() {
	cin >> n >> k;
	for(int i=0; i<n; i++) {
		cin >> c[i];
	}
	
	dp[0]=1;
	for(int j=0; j<n; j++ ) {
		for(int i=1; i<=k; i++) {		
			if(i>=c[j]) {
				dp[i] = dp[i] + dp[i-c[j]];
			}
		}
	}
	cout << dp[k]; 
}

 

점화식

if(i>=c[j]) {
	dp[i] = dp[i] + dp[i-c[j]];
}

 

간단 풀이

 

> 해당 문제에서 for의 순서만 바꾸면 된다.