[BOJ][C++] ๋ฐฑ์ค€ 9084๋ฒˆ: ๋™์ „

2025. 5. 22. 02:30ยท๐Ÿ’ญ Problem Solving/C++

๋ฌธ์ œ

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
'๐Ÿ’ญ Problem Solving/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [BOJ][C++] ๋ฐฑ์ค€ 12865๋ฒˆ: ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ
  • [BOJ][C++] ๋ฐฑ์ค€ 11559๋ฒˆ: Puyo Puyo
  • [BOJ][C++] ๋ฐฑ์ค€ 2606๋ฒˆ: ๋ฐ”์ด๋Ÿฌ์Šค
  • [BOJ][C++] ๋ฐฑ์ค€ 1303๋ฒˆ: ์ „์Ÿ - ์ „ํˆฌ
0=2.
0=2.
  • 0=2.
    0=2
    0=2.
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (56)
      • ๐Ÿ“‚ Project (2)
        • Paint the City (2)
      • ๐Ÿ’ญ Problem Solving (28)
        • C++ (28)
      • ๐Ÿ“ Study (6)
        • Web Front-End Basic (6)
      • ๐Ÿ’ป CS (2)
        • ๐Ÿ“˜ Dev Book (2)
        • ๐Ÿ“ฐ IT News & Research (0)
      • ๐Ÿƒ‍โ™€๏ธ Activities (18)
        • 42 Cursus (18)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
    • ๊ธ€์“ฐ๊ธฐ
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    github
    ํ—ค๋”ํŒŒ์ผ
    BFS
    dynamic programming
    ๋ธŒ๋ฃจํŠธํฌ์Šค
    CSS
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜
    ์ •๋ ฌ
    C
    ์‹œ๋ฎฌ๋ ˆ์ด์…˜
    ๋ฐฑ์ค€
    ๋งต
    dfs
    42๊ฒฝ์‚ฐ
    CS
    knapsack
    makefile
    HTML
    JavaScript
    La Piscine
    ๋ฐฑํŠธ๋ž˜ํ‚น
    ๊ตฌํ˜„
    .h
    VR
    unity
    git
    swea
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
0=2.
[BOJ][C++] ๋ฐฑ์ค€ 9084๋ฒˆ: ๋™์ „
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”