백준 28071 - 승형이의 사탕 사기 (C++)

문제

• 문제 링크

  
   BOJ 28071 - 승형이의 사탕 사기 
  

• 문제 요약

$N$개의 사탕 상자에서 최대 $M$개의 사탕을 가져가려 한다.
고른 총 사탕 개수가 $K$로 나누어 떨어져야 할 때, 가져갈 수 있는 최대 사탕 개수를 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, M, K ≤ 300$

$1 ≤ N_i ≤ 300$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 배낭 문제(knapsack)

풀이

이 문제 역시 $knapsack$ $DP$로 쉽게 해결할 수 있다.

얼마 전 BOJ 28082 - 기계오리 연구 를 다룰 땐,
각 배터리가 $1$개임에 따라 (현재 시행이 현재 시행에 영향을 주지 않기 위해) 뒤에서부터 조사를 진행 했었다.

그러나 이번엔 각 사탕의 개수가 무한하기 때문에 앞부터 진행해도 무방하다.

---

구체적으로

$dp[x] :$ 사탕을 총 $x$개 가져가기 위해 필요한 사탕 상자

라고 정의할 때, 임의의 $N_i$와 $N_i ≤ j ≤ 90,000$ 인 $j$에 대해

$dp[j] =$ $min(dp[j], dp[j - N_i] + 1)$

로 정리할 수 있다.

이후 최댓값을 찾아야 하므로 $90,000$부터 하나씩 내려오며 조건 검사를 진행해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <int> dp(90001, 1e9);
int n, m, k;
 
int main()
{
    cin >> n >> m >> k; dp[0] = 0;
    for (int i; n--;)
    {
        cin >> i;
        for (int j(i); j < 90001; j++)
            dp[j] = min(dp[j], dp[j - i] + 1);
    }
    for (int i(90000); !!~i; i--)
        if (!(i % k) && dp[i] <= m)
            cout << i, exit(0);
}

comment

출제자분은 내심 $bfs$로 풀어주길 기대하며 출제 하셨다고 한다.
하지만 누구도 그러지 않았다고...