문제 풀이/백준
BOJ 2293번: 동전 1
danbibibi
2022. 12. 7. 08:12
문제
문제 바로가기> BOJ 2293번: 동전 1
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
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();
}