저도 별로 아는 게 없는지라 딱 찝어서 어디가 잘 못 되었다고 설명하기 힘드네요.
동전이 오름차순으로 sorting 되어 있기 때문에, 저는 요런 방식으로 했습니다.
동전이 1, 2 원이 있고, 10 원이 목표치이면
memo[0] = 1 memo[1..10] = 0 이고, coin[0] = 1 이고, coin[1] = 2 인 상태
memo[price] 는 price 를 만들 수 있는 동전의 개수 이고,
제일 적은 동전부터 price 를 만들 수 있는 경우의 수를 채워줍니다.
다음 동전이 시작될 때는 이전에 있었던 경우의 수 + 자기 자신으로 표현되는 1 가지 방법으로 시작해서
price 가 될 때까지의 경우를 수를 더해 갑니다.
for (int i = 0; i < N; i++) {
for (int k = coin[i]; k <= price; k++) {
memo[k] = memo[k] + memo[k - coin[i]];
}
}
* 문제 설명에 경우의 수가 int 로 처리 된다고 써 있습니다.
* 동전1 랑 풀이 방식이 같습니다. 이거 풀면 동전1도 그냥 푸시면 됩니다.
jjuguk2 7년 전
아래와 같은 코드로 작성하였는데요,
주어진 샘플 케이스는 맞는데 올리니 계속 fail 이네요...
잘못된 부분이 보이면 조언 부탁드립니다.
#include <stdio.h>
int testcase = 0 ;
int MoneyNum[11]; //동전의 가지수
int Input[11][21]; //각 case에 해당하는 금액
int MakeMoney[11]; //만들어야 할 금액
long long DP[10001];
void Init()
{
for(int i =0 ; i<10001; i++)
DP[i] = 0;
}
int main()
{
scanf("%d",&testcase);
long long temp = 0;
int DPStart = 0;
//Input 값을 입력 한다.
for(int i = 0; i<testcase; i++)
{
scanf("%d",&MoneyNum[i]);
for(int j=0; j<MoneyNum[i]; j++)
{
scanf("%d",&Input[i][j]);
}
scanf("%d",&MakeMoney[i]);
}
//점화식 D[N] = 정수 N을 Money Num의 합으로 만들수 있는 경우의 수
// DP[N] = DP[N-동전 i] + DP[N-동전 J]
for(int t = 0; t<testcase; t++)
{
Init();
DP[0] = 0;
for(int j = 0; j<MoneyNum[t]; j++)
{
DP[Input[t][j]] += 1;
for(int i = Input[t][j] + 1 ; i<=MakeMoney[t] ; i++ )
{
temp = DP[i-Input[t][j]];
DP[i] = DP[i] + temp;
}
}
printf("%lld",DP[MakeMoney[t]]);
}
return 0;
}