BOJ 2293번: 동전 1

문제

문제 바로가기> BOJ 2293번: 동전 1

2293번: 동전 1

 

풀이

2차원 배열로 풀면 메모리 초과가 발생하므로 1차원 배열로 풀어야 한다.

i원 동전을 사용하여 j원을 만들 때 j-coin[i]의 누적합만 알면 되므로 1차원 배열로 풀 수 있다.

 

#include<iostream>
#define MAX 101
#define MAX_K 10001
using namespace std;

int n, k;
int coin[MAX], dp[MAX_K];

void input(){
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> coin[i];
}

void solution(){ // dp[j] : 가치 j를 만들 수 있는 경우의 수
    for(int i=1; i<=n; i++){
    	if(coin[i] <= k) dp[coin[i]]++;
        for(int j=coin[i]+1; j<=k; j++) dp[j] += dp[j-coin[i]];
    } 
    cout << dp[k];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}