[22115] 창영이와 커피

https://www.acmicpc.net/problem/22115

22115번: 창영이와 커피

<문제>

가격이 전부 동일하다고 생각하면 되므로, 사실상 "[12865]평범한 배낭" 과 비슷하게 풀 수 있다.

가격이 1이라고 생각하고, 가격을 최소화하는 느낌으로 접근하자.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = INT_MAX >> 1;

int n, k, dp[100001], w[101];

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> k;

    int i, j;

    fill(&dp[1], &dp[100001], INF);

    for (i = 0; i < n; i++) cin >> w[i];

    for (i = 0; i < n; i++)

        for (j = k; j >= w[i]; j--) dp[j] = min(dp[j - w[i]] + 1, dp[j]);

    if (dp[k] != INF)

        cout << dp[k];

    else

        cout << -1;

    return 0;

}