[白俊]2293号硬貨1
[白俊]2293号硬貨1
質問リンク:https://www.acmicpc.net/problem/2293
問題とI/O
質問へのアクセス
これはdp問題です.この問題は考えてみると単純だ.創造すべき価値(円)はdp配列に格納されて使用される.まずゼロ元のコインがあると仮定して、ゼロから始めます.したがってdp[0]=1であり、各硬貨を計算した.現在の価値は現在の価値から現在の硬貨の価値を差し引くことができる.
dp[i] = dp[i] + dp[i-coin[cur]]
コード実装(C++)
#include <iostream>
#include <cstring>
using namespace std;
int dp[10001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n,k;
cin >> n >> k;
int coin[n];
for(int i = 0 ; i < n ; i++){
cin >> coin[i];
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 0 ; i < n ; i++){
for(int j = coin[i] ; j <= k ; j++){
dp[j] = dp[j] + dp[j-coin[i]];
}
}
cout << dp[k] << "\n";
}
Reference
この問題について([白俊]2293号硬貨1), 我々は、より多くの情報をここで見つけました
https://velog.io/@kpg0518/백준-2293번-동전1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
#include <cstring>
using namespace std;
int dp[10001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n,k;
cin >> n >> k;
int coin[n];
for(int i = 0 ; i < n ; i++){
cin >> coin[i];
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 0 ; i < n ; i++){
for(int j = coin[i] ; j <= k ; j++){
dp[j] = dp[j] + dp[j-coin[i]];
}
}
cout << dp[k] << "\n";
}
Reference
この問題について([白俊]2293号硬貨1), 我々は、より多くの情報をここで見つけました https://velog.io/@kpg0518/백준-2293번-동전1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol