[C++] 백준 - 2293 : 동전 1

문제 링크

2293번: 동전 1

 

풀이 ) DP

  동전의 순서가 답에 영향을 미칠 수 있기 때문에 각 동전에 따라 반복문을 돌린다.

  첫 번째 동전으로 만들 수 있는 k 이하의 금액을 확인하고 그다음 두 번째 동전까지 사용했을 때 만들 수 있는 금액을 확인하고 하는 방식으로 구현을 했다.

 

  처음 구현했을 때 //check 부분에서 memo[coin[i]]++; 을 했었는데 그렇게 되면 예제 입력을 실행할 경우 첫 번째 동전으로 만드는 금액에서 2, 3번째 동전을 사용한 경우가 추가로 더해지기 때문에 정답이 나오지 않았다.

  입력 예제의 경우 i = 0일 때 memo[j]가 모두 1이 되어야하는데 memo[2]가 2가 되어서 다른 숫자에 영향을 미치게 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[100002];

int main(void)
{
  int n, k, coin[102] = {0, };
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; ++i)
    scanf("%d", coin+i);
    // check

  for(int i = 0; i < n; ++i){
    memo[coin[i]]++;
    for(int j = 1; j <= k; ++j)
      if(j > coin[i])
        memo[j] += memo[j-coin[i]];
  }

  printf("%d\n", memo[k]);
  return 0;
}

 

주의점 )

  바깥 for문을 k번 반복하고, 안쪽 for문을 n번 반복하게 구현한다면 순서를 바꿨을 때 중복이 생기는 경우가 있어서 오답이 나온다.

  3원을 만들 때 1원+2원과 2원+1원이 각각 다른 경우로 분류된다.