2293번 동전 1
문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.
예제 입력
3 10
1
2
5
예제 출력
10
해결방법
동전 교환 알고리즘
을 적용한 DP 문제이다처음 접하는 문제인터라 다른 블로그에서 점화식을 참고했다
⭐️ 솔루션 ⭐️
C(i) : i 번째 동전의 가치
D(i, k) : i 번째까지의 동전을 사용하여 k원을 만들 수 있는 경우의 수
- 첫번째 동전만 사용했을때, 1~k 원까지 만들 수 있는 경우의 수를 찾는다
- 두번째 동전을 추가하여, 1~k 원까지 만들 수 있는 경우의 수를 갱신한다
- 1 ~ n 번 동전을 사용했을 때, 1~k 원까지 만들 수 있는 경우의 수를 갱신한다
점화식은 아래와 같다
D(i,k)
{
[C(i) > k] D(i-1,k)
[C(i) ≤ k] D(i-1,k) + D(i,k-c(i))
}
소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
int c[101];
int d[10001];
void dp(){
d[0] = 1;
for(int i=1; i<=n; i++){
for(int j=1; j<=k; j++){
if(c[i] <= j){
d[j] = d[j] + d[j-c[i]];
}
}
}
cout << d[k] << "\n";
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for(int i=1; i<=n; i++){
cin >> c[i];
}
dp();
return 0;
}
'Algorithm > BOJ 문제풀이' 카테고리의 다른 글
[DP] 9251번 LCS (0) | 2019.02.07 |
---|---|
[DP] 2294번 동전2 (0) | 2019.02.06 |
[DP] 11052번 카드 구매하기 (0) | 2019.02.06 |
[DP] 1699번 제곱수의 합 (0) | 2019.02.06 |
[DP] 1535번 안녕 (0) | 2019.02.06 |