반응형
https://algospot.com/judge/problem/read/COINS
algospot.com :: COINS
Coin Change 문제 정보 문제 우리 나라에는 10원, 50원, 100원, 500원의 네 가지 동전이 있다. (1원짜리와 5원짜리는 거의 안 쓰니까 없는 걸로 하지요) 이 동전들을 이용해 110원을 거슬러 주는 방법은 몇
algospot.com
DP문제임.
최대 M값이 5000이므로 모든 경우의 수를 계산하여 품.
가장 작은 동전의 종류부터 DP배열에 더해감.
DP배열은 이전에 계산된 DP배열 값에 새로 추가된 동전 DP값을 더하여 만듬.
#define MAX_COIN 5000
using namespace std;
int main()
{
int T;
for (scanf("%d", &T); T > 0; T--)
{
int M, C;
vector CA;
//DP
long long DP_C[MAX_COIN + 1] = { 0, };
scanf("%d %d", &M, &C);
for (int i = 0; i < C; i++){
int V;
scanf("%d", &V);
CA.push_back(V);
}
sort(CA.begin(), CA.end());
for (int i = 0; i < C; i++)
{
int currentCoin = CA[i];
if (currentCoin > M) break;
++DP_C[currentCoin];
for (int j = 1; currentCoin + j <= M; j++)
{
if (DP_C[j] >= 1)
DP_C[j + currentCoin] += DP_C[j];
}
}
printf("%lld\n", DP_C[M] % (long long)1000000007);
}
return 0;
}반응형