BOJ 2293번 :: 동전 1

#문제

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

#작성 코드

#include <iostream>
using namespace std;
 
int n, k;
int coin[101];            // 인덱스 1~100 사용 
int count[10001];        // [k]원을 만드는 경우의 수 저장. 
 
int main(){
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>coin[i];
    }
    
    count[0]=1;            // 0원을 만드는 경우의 수 1. 
    
    // 1번인덱스의 coin부터 시작.
    // 가치 k를 만드는 경우의 수를 구해서 count[k]에 누적한다. 
    for(int i=1; i<=n; i++){
        for(int j=coin[i]; j<=k; j++){
            count[j] += count[j-coin[i]];
        }
    }
    cout<<count[k]<<'\n';
    return 0;
}

##

2차원 dp를 사용하면 시간이 너무 오래 걸린다!

재귀를 사용해도 시간이 너무 오래 걸린다!

-> coin[i]에 대해 계산한 경우의 수에 coin[i+1]로 계산한 경우의 수를 더해서 덮어씌운다.

 

ex) 3개의 동전(1, 2, 5)으로 가치의 합 10을 만들어야 하는 경우.

업데이트 되는 부분부터 ( for(int j=coin[i]; j<=k; j++) 부분 ), 업데이트 되는 부분만( += d[j-coin[i]] ) 표시했다.

원	1	2	3	4	5	6	7	8	9	10
1	1	11	111	1111	11111	111111	1111111	11111111	111111111	1111111111
2		2	2 1	2 11 2 2	2 111 2 2 1	2 1111 2 2 11 2 2 2	2 11111 2 2 111 2 2 2 1	2 111111 2 2 1111 2 2 2 11 2 2 2 2	2 11111111 2 2 11111 2 2 2 111 2 2 2 2 1	2 11111111 2 2 111111 2 2 2 1111 2 2 2 2 11 2 2 2 2 2
5					5	5 1	5 11 5 2	5 111 5 2 1	5 1111 5 2 11 5 2 2	5 11111 5 2 111 5 2 2 1 5 5
계	1	2	2	3	4	5	6	7	8	10