백준 28082 - 기계오리 연구 (C++)

문제

• 문제 링크

  
   BOJ 28082 - 기계오리 연구 
  

• 문제 요약

배터리 $N$개와 장착할 수 있는 최대 배터리 개수 $K$, 각 배터리의 전력량이 주어진다.
$K$개를 넘지 않는 배터리들을 적절히 조합하여 전력량을 표현할 때, 표현 가능한 종류를 모두 구해보자.

• 제한

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




$1 ≤ N, I_i ≤ 500$

$1 ≤ K ≤ min(N, 100)$

알고리즘 분류

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

풀이

각 배터리의 포함 유무로 표현할 수 있는 전력량의 모든 경우를 구해야 한다.
문제의 제한을 보면, 표현할 수 있는 최대 전력량은 $500 * 100 = 50,000$ 이다.

이는 결국 각 배터리가 $1$개임에 따라, 뒤에서부터 보는 $1$차원 $knapsack$ $DP$ 로 쉽게 조사할 수 있다.

임의의 전력량을 표현하기 위해 다양한 조합이 있을 수 있지만, 우리에게 중요한 건 몇 개의 배터리가 사용 됐냐이다.
그리고 이 질문에 대해선 당연히 최소 개수만을 썼을 때가 우선시 된다.

이에 따라 다음과 같이 정의해보자.

$dp[x] :$ 전력량 $x$를 표현하기 위해 사용되는 배터리의 최소 개수

---

기저 상태로, $dp[0]$을 $0$으로 잡고 나머지 $1$ ~ $50,000$에 대해선 $INF$로 채워 주자.

그럼 어떤 배터리의 전력량 $I_i$와 $(0 ≤ j ≤ 50,000 - I_i)$ 인 $j$에 대해,

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

로 간단하게 식을 정리할 수 있다.

이후 $dp[x] ≤ K$ 인 요소들을 고려해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 50001
using namespace std;
 
vector <int> dp(N, 999);
int n, k, r;
 
int main()
{
    cin >> n >> k;
    for (dp[0] = 0; n--;)
    {
        int i; cin >> i;
        for (int j(N - i - 1); !!~j; j--)
            dp[j + i] = min(dp[j + i], dp[j] + 1);
    }
 
    for (int i(1); i < N; i++)
        r += dp[i] <= k;
    cout << r << '\n';
 
    for (int i(1); i < N; i++)
        if (dp[i] <= k)
            cout << i << ' ';
}

comment

$BitSet$을 이용한 $DP$로도 간단히 풀리는 듯 하다.