[BOJ 9084] 동전

- 문제 요약

 

동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스의 첫 번째 줄에는 동전의 가지 수 N(1<=N<=20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액(1~10,000원)이 오름차순으로 정렬되어 주어진다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1<=M<=10000)이 주어진다.

(같은 동전이 여러 번 주어지는 경우는 없다. 방법의 수는 2^31-1보다 작다.)

 

 

- 알고리즘 정리

 

DP[i] (i원을 만들 수 있는 방법의 수)

DP[i] = DP[i] + DP[i - (동전의 금액)]

 

 

- 코드 작성

 

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

#define MAX 10001
typedef long long ll;
int t,n,m,arr[21],dp[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		cin>>n;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			cin>>arr[i];
		}
		cin>>m;
		dp[0]=1;
		for(int i=1;i<=n;i++){
			for(int j=arr[i];j<=m;j++){
				dp[j]=dp[j]+dp[j-arr[i]];
			}
		}
		cout<<dp[m]<<endl;
	}	
}

코드 제출 결과