https://www.acmicpc.net/problem/6126
6126번: Cow Cash
The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units
www.acmicpc.net
#문제 간단 정리
일종의 배낭문제
#문제 해결 방법
dp[i] = 금액을 만들 수 있는 가지수
즉 dp[i] = dp[i-coin들의 종류] 를 해주면 된다
여기서 주의할것은 코인을 1+2 와 2+1 는 중복되는 것이기 때문에 이를 고려해 주어야 한다
for (int i = 1; i <= N; i++) {
for (auto coin : coins) {
if (i - coin >= 0) {
dp[i] += dp[i - coin];
}
}
}
이렇게 써버리면 순서에 따라서 중복이 나오고
for (auto coin : coins) {
for (int i = coin; i <= N; i++) {
dp[i] += dp[i - coin];
}
}이렇게 써서 중복이 안나오도록
작은 순서부터 코인을 쓰도록 해야 중복을 피할 수 있다.
#전체 코드
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <tuple>
#include <sstream>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int V, N;
cin >> V >> N;
vector<int> coins(V);
vector<int> dp(N+1, 0);
dp[0] = 1;
for (int i = 0; i < V; i++) {
cin >> coins[i];
}
//dp[i] i금액을 만들 수 있는 가짓수 / dp[i] = dp[i-coins]
/* for (int i = 1; i <= N; i++) {
for (auto coin : coins) {
if (i - coin >= 0) {
dp[i] += dp[i - coin];
}
}
}*/
for (auto coin : coins) {
for (int i = coin; i <= N; i++) {
dp[i] += dp[i - coin];
}
}
cout << dp[N] << '\n';
return 0;
}
'[백준] > C++' 카테고리의 다른 글
백준 1261번 알고스팟 [C++] (0) | 2024.04.14 |
---|---|
백준 1584번 게임 [C++] (0) | 2024.04.12 |
백준 4949번 균형잡힌 세상 [C++] (0) | 2024.04.03 |
백준 2357번 최솟값과 최댓값 [C++] (0) | 2024.03.30 |
백준 1920번 수 찾기 [C++] (0) | 2024.03.24 |