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;
}

sgchoi5   7년 전

저도 별로 아는 게 없는지라 딱 찝어서 어디가 잘 못 되었다고 설명하기 힘드네요. 

동전이 오름차순으로 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도 그냥 푸시면 됩니다. 

댓글을 작성하려면 로그인해야 합니다.