[구름LEVEL] 별들의 전쟁

난이도	정답률
★★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 4주차

goorm

문제

생산 가능한 인구 수가 주어졌을 때 최소한의 유닛을 이용하여 해당 인구 수를 정확히 맞추는 사람이 승리한다. '별들의 전쟁'의 모든 유닛에는 인구 수라는 수치가 주어졌으며, 유닛을 생산할 때 그 유닛에 맞는 인구 수만큼 인구 수가 증가한다.

특정 종족의 유닛들을 생산하면 인구 수를 차지하는지, 승리하를 위해 필요한 인구 수가 몇인지 주어졌을 때, 생산해야 하는 최소 유닛 수를 구해보자!

해당 종족의 유닛수 N(1 ≤ N ≤ 100), 승리를 위해 필요한 인구 수 K(1 ≤ K ≤ 10,000)

해결

key point, dp[i] = dp[i-unit] + 1

1. '유닛을 생산했을 때 얼마만큼의 인구 수를 차지하는 가'가 주어졌을 때 units에 넣어두고
2. units을 정렬한 후 중복이 있다면 제거한다.
   👉 두 개의 다른 유닛이 같은 인구 수를 차지한다면 하나의 유닛으로 바꾼 후 최소 유닛 수를 구한다.
3. dp[i]는 '인구 수 i를 만드는 최소 유닛 수'이다.
4. dp[]를 정의해뒀다면 반복문을 돌린다.
   1. 각각의 유닛에 대하여 인구 수가 작은 것 부터 반복문을 돌린다. → unit (현재 보고있는 유닛의 인구 수)
   2. unit부터 k까지 반복문을 돌린다 → i (만들고 싶은 인구 수)
   3. i와 unit이 같다면, 유닛의 인구 수와 만들고 싶은 인구 수가 같다는 것으로 유닛 한 개로 만들 수 있다.
   4. 그 외의 경우에는, 유닛의 인구 수로 i를 만드는 최소 유닛 수는 'i-unit개의 인구를 만드는 최소 유닛 수'에 1을 더한 것과 같다.
      👉 1을 더하는 이유는 dp[unit]을 더하는 것과 같은데 어차피 dp[unit]은 위의 i==unit의 경우와 같으므로 항상 1이다.
5. 이렇게 unit으로 i를 만드는 최소 유닛 수는 ⚡ dp[i] = dp[i-unit] + 1 ⚡가 된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, dp[10005];
vector<int> units;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, a; i < n; i++) {
        scanf("%d", &a);
        units.push_back(a);
    }
    sort(units.begin(), units.end());
    units.erase(unique(units.begin(), units.end()), units.end());
    for (auto unit : units) {
        for (int i = unit; i <= k; i++) {
            if (i == unit)dp[i] = 1;
            else if (dp[i - unit] > 0) dp[i] = dp[i] ? min(dp[i], dp[i - unit] + 1) : dp[i - unit] + 1;
        }
    }
    printf("%d", dp[k] ? dp[k] : -1);
    return 0;
}

 

후기

유명한 동전문제와 비슷하다고 생각해서 빨리 풀긴했지만 처음 코드는 runtime error가 났다..

다른 점은 unit에 대해서 인구 수 k를 반복할 것인지, k에 대해서 unit을 반복할건지 반복문 순서만 다른데..
이유는 아직도 모르겠다.

혹시 왜 runtime error인지 알겠거나 의심이 간다면 댓글 남겨주세요!

for (int i = units[0]; i <= k; i++) {
    for (auto unit : units) {
        if (i - unit < 0) continue;
        if (i == unit) dp[i] = 1;
        else if (dp[i - unit] > 0) dp[i] = dp[i] ? min(dp[i], dp[i - unit] + 1) : dp[i - unit] + 1;
    }
}