C - 백준 2293번. 동전1

input: n (동전의 종류), k (만들어야 하는 동전 가치의 합)

          각각의 동전의 가치 입력

output: 만들 수 있는 경우의 수

 

예제)

input

output

주요 해결 알고리즘: Dynamic Programming

예제의 경우를 가지고 생각해보자.

i \ k	동전	0	1	2	3	4	5	6	7	8	9	10
0	0	1	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	1	1	1
2	2	1	1	2	2	3	3	4	4	5	5	6
3	5	1	1	2	2	3	4	5	6	7	8	10

 

한 줄씩 생각하면 쉽다.

이 표를 완전히 이해하는게 포인트다!

 

k=0) k값이 0일때 의미하는 것은 , 0원으로 k원을 표현할 수 있는 방법을 의미한다. 0원으로는 나타낼 수 있는 방법이 없기 때문에 k=0을 제외하고는 모두 0이 들어간다.

k=1) coin[1]을 의미, 즉 동전이 1원인 경우이다.

       만약 k가 1일때를 생각해 보면, 0원을 구하는 경우의 수와 같다. -> value[k] = value[k-1];

       k가 2일 때, 2에서 1을 빼면 1이 나오므로 1원을 구하는 경우의 수와 같다. -> value[2] = value[1];

       k가 3일 때, 3에서 1을 빼면 2가 나오므로 2원을 구하는 경우의 수와 같다. -> value[3] = value[2]; 

       .......

k=2) coin[2]를 의미, 즉 동전이 2원인 경우

       k가 1일 때, 1은 2원보다 작기 때문에 2원으로 표현할 수 없다. 그러므로 1원을 가지고 나타낼 수 있는 경우의 수가 곧 k가 1일 때의 경우         의 수가 된다.

       k가 2일 때, 2에서 2를 빼면 0이 나온다, 즉 2+0 인 경우이다. 여기서 알 수 있듯이 k가 0일때 경우의 수가 1인 이유는 자기 자신과 0으로 나타내 질 경우를 의미한다. 1을 사용해서 구할 수 있는 경우의 수와 0일 때의 경우의 수를 더한다 -> value[2] = value[2] + value[0]

      k가 3일 때, 3에서 2를 뺀 1일 때의 경우의 수를 가져온다. 그리고 1을 사용해서 구할 수 있는 경우의 수를 더한다.

-> value[3] =  value[3] + value[1]

.....

k=3일 때도 똑같은 과정을 반복한다.

 

점화식

value[k] = value[k]    if k < coin[i]

value[k] = value[k] + value[k-coin[i]]  if k >= coin[i]

 

#include <stdio.h>

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  int value[k+1];
  int coin[n+1];

  coin[0] = 0;
  for(int i=1 ; i<n+1 ; i++) {
    scanf("%d", &coin[i]);
  }
  for(int i=0 ; i<k+1 ; i++) {
    value[i] = 0;
    if(i==0)  value[i] = 1;
  }

  for(int i=1 ; i<n+1 ; i++) {
    int Coin = coin[i];
    for(int j=0 ; j<k+1 ; j++) {
      if(j==0) {
        value[j] = 1;
      }
      else
      {
        if( j >= Coin ) {
          value[j] += value[j-Coin];
        }
      }
    }
  }
  printf("%d \n", value[k]);
}

 

점화식을 세우는게 정말 중요한 키 포인트인것 같다.

무작정 for문이고 뭐고 코드부터 짜려고 하지 말고 규칙을 똑바로 찾아서 점화식을 세우는 연습을 해야겠다!