「AOJ Problem Set from DPL 問0~4」の編集履歴(バックアップ)一覧に戻る

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 03:46:40) のソース

*Combinatorial - Coin Changing Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A
金額を払うのに必要な最小コイン枚数をDPで解く問題。

 #include<stdio.h>
 #include<vector>
 
 int main(){
 	int n,m,memo[50001]={0};
 	scanf("%d %d",&n,&m);
 	int coin;
  	for(int i=0;i<m;i++){
 		scanf("%d",&coin);
 		for(int j=0;j+coin<=n;j++){
 			if(memo[j]==0&&j>0)continue;
 			if(memo[j+coin]==0||memo[j+coin]>memo[j]+1){
 				memo[j+coin]=memo[j]+1;
 			}
 		}
  	}
 	printf("%d\n",memo[n]);
 }