๋ฌธ์
https://www.acmicpc.net/problem/9084
๋ฌธ์ ์ดํด
N๊ฐ์ง ๋์ ์ผ๋ก ๊ธ์ก M์ ๋ง๋๋ ๋ชจ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ค.
๋ฌธ์ ํ์ด
๐ ์ ๊ทผ
์ด ๋ฌธ์ ๋ ๋ํ์ ์ธ Unbounded Knapsack ๋ฌธ์ ๋ค.
์๋์ ๋ฐฐ๋ญ ๋ฌธ์ ์์ ๊ฐ ๋ฌผ๊ฑด์ 1๋ฒ๋ง ์ ํํ ์ ์์๋ ์ ๊ณผ ๋ค๋ฅด๊ฒ, ๊ฐ์ ๋์ ์ ์ฌ๋ฌ๋ฒ ๋ฃ์ ์ ์๋ค.
[BOJ][C++] ๋ฐฑ์ค 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ
๋ฌธ์ https://www.acmicpc.net/problem/12865 ๋ฌธ์ ์ดํด์ต๋ ๋ฌด๊ฒ(K)๊ฐ ์ ํด์ง ๋ฐฐ๋ญ์ ๋ฌผ๊ฑด์ ๋ฃ๋๋ค. N๊ฐ์ ๋ฌผ๊ฑด์๋ ๊ฐ๊ฐ ๋ฌด๊ฒ(W)์ ๊ฐ์น(V)๊ฐ ์๋ค.๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์นํฉ์ ์ต๋๊ฐ์ ๊ตฌํ๋ค.
y-e-99.tistory.com
๐ก Dynamic Programming
- ๋ชฉํ ๊ธ์ก์ ์ธ๋ฑ์ค๋ก, ๋ชฉํ ๊ธ์ก์ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ ์ฅํ๋ค.
- ์์ ๊ธ์ก์ ๋ง๋๋ ๋ฐฉ๋ฒ๋ถํฐ ์ฑ์๋๊ฐ๋ค.
- 0์์ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ 1์ด๋ค.
dp[0] = 1
๐ก Bottom-up DP
j๋ฅผ ๋ง๋ค๊ธฐ ์ํ ์กฐํฉ = (j - coin) ์กฐํฉ + coin ํ๋ ๋
for (int coin: coins) {
for (int j = coin; j <= m; j++)
dp[j] += dp[j - coin];
}
์ฝ๋
#include <iostream>
#include <vector>
using namespace std;
int solution(int n, int m, vector<int> &coins) {
vector<int> dp(m + 1, 0);
dp[0] = 1;
for (int coin: coins) {
for (int j = coin; j <= m; j++)
dp[j] += dp[j - coin];
}
return dp[m];
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
vector<int> coins;
// ์
๋ ฅ
cin >> n;
coins.assign(n, 0);
for (int &i: coins)
cin >> i;
cin >> m;
// ์ถ๋ ฅ
cout << solution(n, m, coins) << '\n';
}
return 0;
}
'๐ญ Problem Solving > C++' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ (0) | 2025.05.19 |
---|---|
[BOJ][C++] ๋ฐฑ์ค 11559๋ฒ: Puyo Puyo (0) | 2025.05.18 |
[BOJ][C++] ๋ฐฑ์ค 2606๋ฒ: ๋ฐ์ด๋ฌ์ค (0) | 2025.05.13 |
[BOJ][C++] ๋ฐฑ์ค 1303๋ฒ: ์ ์ - ์ ํฌ (0) | 2025.04.23 |
[BOJ][C++] ๋ฐฑ์ค 1890๋ฒ: ์ ํ (0) | 2025.04.23 |