반응형
https://www.acmicpc.net/problem/2293
💡 동전 1
✅ 문제 풀이
- 배낭 문제와 접근 방식이 동일하다.
- dp를 이용해 경우의 수를 구해나간다.
- dp[i]=j 는 "n가지 종류의 동전을 이용해서 합이 i원이 되도록 하는 경우의 수가 j개" 라는 뜻이다.
- dp[0]=1이다. 합이 0원이 되는 경우의 수는 아무것도 합하지 않는 경우 1개가 존재하기 때문이다. 따라서 이는 초기값이 된다.
- 만약 동전 종류 중 1원짜리가 있다고 하자. 1원을 가지고 1원을 만드는 경우의 수는 다음과 같다.
dp[1]=dp[1]+dp[0]
1원이 되려면, 0원에다가 1원을 더해주면 되니까 0원이 되는 경우의 수를 합해주면 된다. 따라서 1이다. - 만약 동전 종류 중 3원짜리가 있다고 하자. 3원을 가지고 5원을 만드는 경우의 수는 다음과 같다.
dp[5]=dp[5]+dp[2]
5원이 되려면, 2원에다가 3원을 더해주면 되니까 2원이 되는 경우의 수를 합해주면 된다. - 즉 dp[i]를 구하려면 i에서 동전 가치 "value[j]"를 빼준 값이 되는 경우에다가 그냥 value[j]를 더하면 i원이 되는 거니까. dp[i-value[j]]를 구하는 것과 동일하다. 즉 i-value[j]원이 되는 경우의 수를 구하는 것과 같다.
- 주의할 점은 어떤 value[j]를 가지고서 i원이 되도록 할 때, i는 value[j]보다 커야 한다는 것이다.
예를 들어, 3원을 더함으로써 4원을 만들어낼 수 있지만, 3원을 더함으로써 2원을 만들어낼 수는 없다. 이미 3이라는 가치가 2보다 크기때문에, 3원을 더하려면 항상 3원 이상의 큰 가치만을 만들어 낼 수 있다. - 따라서 다음과 같은 점화식을 따른다.
dp[i]+=dp[i-value[j]]
(이때, i>=value[j]) - 위를 모든 동전의 종류에 대해서 반복해주면 된다.
- 최종 답은 dp[k]이다. k원을 만드는 경우의 수 이기 때문이다.
✏ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
vector<int> value(n);
for (int i = 0; i < n; i++) {
cin >> value[i];
}
vector<long long> dp(k + 1,0); //출력 범위가 2^31 까지 임에 주의하여 long long으로 선언
dp[0] = 1;//0원을 만드는 데 필요한 경우의 수 1
for (int i = 0; i < n; i++) {
for (int j = value[i]; j <= k; j++) {
dp[j] += dp[j - value[i]];//j원을 만드는데, value[i]원을 사용하려면 j에서 value[i]를 뺀 값이 필요하고, 이것의 경우의 수를 더해주면 됨.
}
}
cout << dp[k];
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 1011번 C++ "Fly me to the Alpha Centauri" 풀이 / 수학 (1) | 2024.02.05 |
---|---|
[백준] 15686번 C++ "치킨 배달" 풀이 / 완전 탐색, 조합 / 삼성 sw역량테스트 기출문제 (1) | 2024.02.02 |
[백준] 9251번 C++ "LCS" 풀이 / DP (1) | 2024.01.31 |
[백준] 7569번 C++ "토마토" 풀이 / bfs, 3차원 벡터 (1) | 2024.01.29 |
[백준] 10026번 C++ "적록색약" 풀이 / dfs, 너비 우선 탐색 (0) | 2024.01.27 |