1. 문제
2. 접근 방법
1. 순서는 고려하지 않는다
= 사용한 각 동전의 "개수"가 중요하다.
= 사용한 동전의 개수 기준으로 경우의 수 나누기
2. 경우의 수를 구하라
1) 아래 두 가지 중 더 접근하기 쉬운 것이 무엇인지를 인지하면서 점화식 구해보기
return 1 + foo(n-1) 형식으로 접근하는 법 (1가지 경우의 수 씩 count)return foo(n-1) + ...foo(n-2) 등 n-1과의 점화식으로 접근하는 법
2) 경우의 수 만드는 기준 정하기 어려울 때
: 문제에서 input으로 주어진 값들을 기준으로 하기 or 값의 범위가 더 제한적인 것을 기준으로 하기
ex) 이 문제에선 사용할 수 있는 동전의 가치가 연속(1,2, ... , n)이 아니라 주어진 값만 쓸 수 있다.(제한적임)
따라서 사용할 수 있는 동전의 가치들의 조합으로 K를 만들자
3. 점화식 구하기
1) 예제 1의 풀이법 이해하기 (1,2,5원으로 10원 만들기 )
- 1원 만들기 : 1 (1)
- 2원 만들기 : 1+1 , 2 (2)
- 3원 만들기 : 1+1+1 , 1+ 2 (2)
- 4원 만들기 : 1+1+1+1, 1+1+2 , 2+2 (3)
- 5원 만들기 : 1+1+1+1+1,1+1+1+2, 5 (4)
= 5원 만드는 경우를 잘 보면, 1원 + 4 , 2원 + 3, 5원 + 0 으로 나눌 수 있다. 즉, 1원을 더해서 완성시키는 경우, 2원을 더해서 완성시키는 경우, 5원을 더해서 완성시키는 경우, 총 3가지 경우의 수를 고려해야 한다.
중복이 되면 안되므로 1원으로 만들 수 있는 경우의 수를 K원까지 구하고, 1원 + 2원으로 만들 수 있는 경우의 수를 K원까지 구하고, 1+2+5원으로 만들 수 있는 경우의 수를 K원까지 구하는 방식으로 진행한다.
coins[i]가 이번에 추가해서 만들어 볼 동전의 가치이고(예제 1로 본다면 coins[0] =1, coins[1] = 2,coins[2] = 5) , j가 이번에 만들 금액이라고 하자.
- dp[j] = dp[j](이전의 동전 종류를 이용해 j를 만드는 경우의 수) + dp[j - coins[i]](새 동전을 사용하는 경우 추가)
3. 실수
1) core dump 요인
1. dp배열 범위를 k로 함 => 크기를 k+1로 하고 접근 index도 1~k까지로 하자(헷갈리게 하지 않기 위해)
2) 오래 걸린 부분 : 순서 상관 없이 중복 고르는 경우
3) 위 경우처럼 총 K원을 만들 때, i원 + k - i 원 만드는 경우로 생각을 해야 한다. 이 때 5에 특히 집중하기(4나 6은 2+2, 3+3의 경우도 있어서 개인적으론 헷갈렸다..)
4. 코드
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
int n, k;
int coin[100],dp[10001] = {1,0,}; //dp[0] = 1
cin >> n >> k;
for(int i=0;i<n;i++) cin >> coin[i];
for(int i=0;i<n;i++) {
for(int j=1;j<=k;j++) {
if(j - coin[i] >=0 ) dp[j] += dp[j-coin[i]];
}
}
cout<<dp[k]<<endl;
return 0;
}