[백준 2293] 동전1

www.acmicpc.net/problem/2293

2293번: 동전 1

dp를 사용하는데 점화식 세우는 데에 애먹었다. ㅠㅠ

주어진 동전을 기준으로 경우의 수를 세는 것이 문제의 핵심이다. 

 

접근:

주어진 예시에서 1 2 5의 동전이 주어졌다고 했다.

1의 동전을 사용하면 k=10에 도달하기 까지 경우의 수가

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

모두 1이 될 것이다.

그 다음 2의 동전을 사용해보자.

1의 경우 2보다 작으니까 2의 동전을 사용해서 만들 수 없다. 2부터 진행하는데 2는 2하나로 만들 수 있다. 그래서 dp[0]=1로 초기화 해주고 dp[2] = dp[2] + dp[2-2];라고 할 수 있다.

3도 마찬가지. 1만 사용해서 만드는 방법 1가지 + 2를 사용해서 만드는 방법(dp[3-2]) 가 될 것이다.

 

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

 

그 다음 5의 동전을 사용해보자. 1~4까지는 영향을 안받는다.

5의 경우 dp[5] = dp[5] + dp[5-5] = 4이다.

6의 경우 1과 2를 사용해서 만드는 방법이 4가지 + 5를 사용해서 만드는 방법(dp[6-1])이 될 것이다.

 

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	5	6	7	8	10

 

c++로 확인한다면

#include <stdio.h>

using namespace std;

int coins[100];
int dp[10000 + 1];
int main(void)
{
  int n, k;
  scanf("%d%d", &n, &k);

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &coins[i]);
  }
  dp[0] = 1;
  for (int i = 0; i < n; i++)
  {
    for (int j = coins[i]; j <= k; j++)
    {
      dp[j] += dp[j - coins[i]];
    }
  }
  printf("%d\n", dp[k]);
  return 0;
}