💡 문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.
🤔 내가 생각한 아이디어
문제를 통해 이해해보기
동전이라고 하길래 그리디부터 생각났다.
무작정 그리디를 쓰려고 했는데… 생각해보니 그러면 안될 것 같다.
앞선 동전 0문제에서는, 동전의 가치들 사이의 배수관계가 성립해서 그리디로 풀 수 있었는데 현재는 동전의 가치들 사이의 배수관계가 성립한다는 이야기가 없으므로 그리디로 풀 수 없겠다는 생각을 했다.
dp로 풀 수 있나? 감이 잘 안잡히지만... 일단 무작정 나열 해봤다.
- dp 테이블 정의
dp[n]=k:
가치의 합이 n원이도록 주어진 동전을 조합하여 만들 수 있는 경우의 수
- dp[1]={1} = 1
- dp[2]={1,1} {2} =2
- dp[3]={1,1,1} {2,1} {1,2} =3
- dp[4]={1,1,1,1} {1,1,2} {2,2} =3
- dp[5]={1,1,1,1,1} {1,1,1,2} {1,2,2} {5}=4
- dp[6]={1,1,1,1,1,1} {1,1,1,1,2} {1,1,2,2} {2,2,2} {1,5}=5
...
이렇게 나열해도 사실 명확한 감이 안오고 모르겠지만,
쓰다보니 이런 점을 발견해서 옆에 메모해놨다.
- dp[1]={1} = 1
→ 만들려고 하는 가치합이 동전가치 1원과 크거나 같으므로 동전가치 1원을 사용할 수 있음- dp[2]={1,1} {2} =2
→ 만들려고 하는 가치합이 동전가치 2원보다 크거나 같으므로 동전가치 1, 2원을 사용할 수 있음- dp[3]={1,1,1} {2,1} {1,2} =3
→ 만들려고 하는 가치합이 동전가치 2원보다 크거나 같으므로 동전가치 1,2원을 사용할 수 있음- dp[4]={1,1,1,1} {1,1,2} {2,2} =3
→ 만들려고 하는 가치합이 동전가치 2원보다 크거나 같으므로 동전가치 1,2원을 사용할 수 있음- dp[5]={1,1,1,1,1} {1,1,1,2} {1,2,2} {5}=4
→ 만들려고 하는 가치합이 동전가치 5원보다 크거나 같으므로 동전가치 1,2,5원을 사용할 수 있음- dp[6]={1,1,1,1,1,1} {1,1,1,1,2} {1,1,2,2} {2,2,2} {1,5}=5
→ 만들려고 하는 가치합이 동전가치 5원보다 크거나 같으므로 동전가치 1,2,5원을 사용할 수 있음
...
아, 만들려고 하는 가치합(n)과 가지고 있는 동전의 가치값(coin[i])을 비교해서,
크거나 같은 것을 기준으로 사용할 수 있는 동전종류의 갯수가 업데이트된다.
⚒️ 뚝딱뚝딱 설계
뭔가 해당 가치를 가지는 동전을 가지는가/가지지 않는가에 따라 업데이트가 되는 것 같다.
지금 우리가 가지고 있는 가치가 {1,2,5}니까,
만약 {1} 가치만 있다고 생각해보자.
1원만 이용해서 가치합 k를 만들 수 있으려면, 당연히 다음과 같을 거다.
근데 여기서,
{1, 2} 가치를 가지고 있다고 가정하고, 이를 이용해서 가치합 k를 만들 수 있으려면?
동전 가치 2원을 기준으로 가치합 k보다 크거나 같을 때, 만들 수 있는 갯수가 업데이트된 걸 볼 수 있다.
그렇다면 어떤 규칙으로 업데이트되는 걸까?
음, 정확히는 자기 기준 2개 앞선 값만큼의 값을 자신에게 더해가며 업데이트한다.
dp[k]=dp[k]+dp[k-(2)]
마찬가지로, {1,2,5} 가치를 가지고 있다면
동전 가치 5원을 기준으로 가치합 k보다 크거나 같을 때, 만들 수 있는 갯수는 업데이트 된다. 정확히 자기 기준 5개 앞선 값만큼의 값을 자신에게 더해가며 업데이트한다.
dp[k]=dp[k]+dp[k-(5)]
그럼, 업데이트하는 시점을 기준으로 다음과 같은 점화식을 이끌어낼 수 있다.
coin[i]가치를 가지는 동전에 대해,
j>=coin[i]일 때
- dp[j]=dp[j]+dp[j-coin[i]]
💻 정답 코드
//2293 동전 1 문제
//dp로 풀 수 있을 것 같다.
//dp[a]=b a원을 만들 수 있는 동전 경우의 수 set은 b
#include <iostream>
using namespace std;
int n, k; //n가지 종류의 동전, 가치의 합이 k원
int dp[10004];
int coin[104]; //동전의 가치
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 0; i < n; i++) {
cin >> coin[i];
}
dp[0]=1;
for(int i = 0; i < n; i++) { //각 동전 가치에 대하여,
for(int j = coin[i]; j<=k; j++) {
dp[j]+=dp[j-coin[i]];
}
}
cout << dp[k];
}