백준(BOJ) 2293 - 동전1

다이나믹 프로그래밍 문제다.

많은 사람들이 풀어서 많은 해법이 나와있었다.

하지만 이해하기 힘든 문제였다.

혼자서는 도저히 생각 할 수 없었고 정답을 보고 이해하는 방법을 택했다.

N개 종류의 동전을 가지고 K원을 만들때,

처음에는 한개종류의 동전을 가지고 0 ~ K원을 만들고

그다음에는 두개종류의 동전을 가지고 0~ K원을 만든다.

그다음에는? 당연히 3개의 동전을 가지고 0 ~ K원을 만든다.

이렇게 만들때에는 당연히 이전에 사용한 값을 이용한다.

만약 1을 이용해 0 ~ K원을 만들었다 치자.

그리고 1 과 2를 이용해서 다시 0~ K원을 만들때를 생각해보자.

1과 2원을 이용해 K가 2원인 경우까지 세었고, 

이제 3원을 만들고 싶다. 현재 1원으로는 만들어봤다.

1원으로 만든경우는 111일테니 이 경우를 더해주자.

2원을 활용해 3을 만들어야하므로 1과 2원을 활용해 1을만든거에 이번에 활용할 2를 추가해주면 3이된다.

그러면 1과 2를 활용하여 3을 만든 것이다.

다시해보자.

1로 0 ~ K 까지 만들었다 생각하자. 

1과 2를 이용해 3까지의 경우의 수를 세었고, 이제 4를 만들고싶다.

1만을 이용한 1111이 있을 것이다.

이 경우를 더해주자. ( + 1)

그리고 1~2를 이용해 2를 만든것에서 (11, 2)에서 2를 추가해주면 4가된다.  ( + 2)

총 세 경우가 저장된다.

다시 다시 다시 해보자.

1과 2원으로 0 ~ K원을 전부 만들었다.

이제 5원을 활용하여 0~ K원을 만들차례이고 K-1원까지 만들었다 생각해보자.

K원을 만들려면 일단 1~2원으로 K원을 만든 경우를 더해주면된다.

그리고 1,2,5로 K-5원까지 만든 경우(경우의 수가 아님)들은 5만 추가하면 K원이 되므로 그 경우의 수도 더해주면 된다.

처음에는 dp를 [100][10001] 을 선언하였었는데, 메모리 초과가 났다.

메모리 제한은 4MB로 4*100*10001에 이것저것 하면 4메가에 넘게된다.

따라서 dp를 dp[2][10001]로 선언하고, 토글변수 next로 이전 값만 저장하도록 구현하였다.

아래는 코드다.

#include <iostream>
#include <cstdio>
 
int arr[102];
int dp[2][10001];
int next = 0;
int main(void){
  int N, K;
  scanf("%d %d", &N, &K);
  for(int i = 0 ; i <N ; i++){
    scanf("%d", arr + i);
  }
  for(int i = 0 ; i< N; i++){
    int n = arr[i];
    for(int j = 0 ; j <= K; j++){
      dp[next][j] = dp[next ^ 1][j];
      if(n == j) dp[next][j]++;
 
      if(j - n > 0){
        dp[next][j] += dp[next][j-n];
      }
    }
    next ^= 1;
  }
  printf("%d", dp[next ^ 1][K]);
 
}