백준 1228번: 전쟁 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

전쟁

풀이

각 나라를 정점으로 생각하면 문제에서 주어지는 나라끼리의 관계는 포레스트로 나타낼 수 있습니다. 이때 포레스트를 이루는 노드의 루트(어느 나라의 속국도 아닌 나라)들의 부모 노드를 하나 만들어서 트리로 나타낼 수 있습니다. 이때 만든 가상의 부모 노드를 $r$이라 합시다.

노드 $u$의 서브트리에서 $i$만큼의 나라를 정복하기 위한 최소 시간을 $DP[u][i]$라 합시다. $u$의 자식 $v$에 대해 $DP[v][i]$를 배낭 문제의 물건처럼 생각하여 $DP[u][i]$를 구할 수 있습니다.

노드 $u$를 정복하는데 걸리는 시간을 $t_u$라 하고, 노드 $u$의 서브트리에 속하는 정점의 개수($u$ 포함)를 $\operatorname{size}(u)$라 합시다.

초기값으로 $DP[u][0] = 0$, $DP[u][\operatorname{size}(u)] = t_u$로 둡시다. 이제 아래의 점화식을 통해 $DP[u][i]$를 구할 수 있습니다.

\[\begin{gather} \text{for}\ 1 \le i \le \operatorname{size}(u), 1 \le j \le \min(\operatorname{size}(v), i) \\ DP[u][i] = \min_{\text{child}\ v}(DP[u][i - j] + DP[v][j]) \end{gather}\]

답은 $\min_{i = M}^N(DP[r][i])$가 됩니다.

각 노드마다 $\operatorname{size}(u) \times \sum\operatorname{size}(v)$만큼의 계산이 필요합니다. $\operatorname{size}(u) = \mathcal{O}(N)$이고 $\sum\operatorname{size}(v) = \mathcal{O}(N)$이므로 시간 복잡도 $\mathcal{O}(N^3)$에 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> nameToIdx = {
    pair("#root", 0)
};

int N, M;

vector<int> childs[222];
vector<string> childNames[222];
int conquestTime[222];
unordered_map<string, bool> isVassal;
int sz[222];
int dp[222][222];

void initSizeOfSubtree(int root) {
    sz[root] = 1;
    for (int child : childs[root]) {
        initSizeOfSubtree(child);
        sz[root] += sz[child];
    }
}

void initDP(int root) {
    for (int child : childs[root])
        initDP(child);

    dp[root][0] = 0;
    dp[root][sz[root]] = conquestTime[root];

    for (int child : childs[root]) {
        for (int i = sz[root]; i >= 1; i--) {
            for (int j = 1; j <= min(sz[child], i); j++) {
                dp[root][i] = min(dp[root][i], dp[root][i - j] + dp[child][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    cin.ignore();
    for (int i = 1; i <= N; i++) {
        string line;
        getline(cin, line);

        string country;
        int j = 0;
        for (; line[j] != ' '; j++)
            country.push_back(line[j]);
        nameToIdx[country] = i;
        childNames[0].push_back(country);

        j++;
        for (; line[j] != ' ' and line[j] != '
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> nameToIdx = {
    pair("#root", 0)
};

int N, M;

vector<int> childs[222];
vector<string> childNames[222];
int conquestTime[222];
unordered_map<string, bool> isVassal;
int sz[222];
int dp[222][222];

void initSizeOfSubtree(int root) {
    sz[root] = 1;
    for (int child : childs[root]) {
        initSizeOfSubtree(child);
        sz[root] += sz[child];
    }
}

void initDP(int root) {
    for (int child : childs[root])
        initDP(child);

    dp[root][0] = 0;
    dp[root][sz[root]] = conquestTime[root];

    for (int child : childs[root]) {
        for (int i = sz[root]; i >= 1; i--) {
            for (int j = 1; j <= min(sz[child], i); j++) {
                dp[root][i] = min(dp[root][i], dp[root][i - j] + dp[child][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    cin.ignore();
    for (int i = 1; i <= N; i++) {
        string line;
        getline(cin, line);

        string country;
        int j = 0;
        for (; line[j] != ' '; j++)
            country.push_back(line[j]);
        nameToIdx[country] = i;
        childNames[0].push_back(country);

        j++;
        for (; line[j] != ' ' and line[j] != '\0'; j++) {
            conquestTime[i] *= 10;
            conquestTime[i] += line[j] - '0';
        }

        while (line[j] != '\0') {
            country.clear();
            j++;
            for (; line[j] != ' ' and line[j] != '\0'; j++)
                country.push_back(line[j]);
            childNames[i].push_back(country);
            isVassal[country] = true;
        }
    }

    for (string name : childNames[0]) {
        if (isVassal[name])
            continue;
        childs[0].push_back(nameToIdx[name]);
    }

    for (int i = 1; i <= N; i++) {
        for (string name : childNames[i])
            childs[i].push_back(nameToIdx[name]);
    }

    initSizeOfSubtree(0);
    fill(&dp[0][0], &dp[N + 1][N + 1], 1e9);
    initDP(0);

    int answer = dp[0][M];
    for (int i = M + 1; i <= N; i++)
        answer = min(answer, dp[0][i]);

    cout << answer;

    return 0;
}

'; j++) {
            conquestTime[i] *= 10;
            conquestTime[i] += line[j] - '0';
        }

        while (line[j] != '
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> nameToIdx = {
    pair("#root", 0)
};

int N, M;

vector<int> childs[222];
vector<string> childNames[222];
int conquestTime[222];
unordered_map<string, bool> isVassal;
int sz[222];
int dp[222][222];

void initSizeOfSubtree(int root) {
    sz[root] = 1;
    for (int child : childs[root]) {
        initSizeOfSubtree(child);
        sz[root] += sz[child];
    }
}

void initDP(int root) {
    for (int child : childs[root])
        initDP(child);

    dp[root][0] = 0;
    dp[root][sz[root]] = conquestTime[root];

    for (int child : childs[root]) {
        for (int i = sz[root]; i >= 1; i--) {
            for (int j = 1; j <= min(sz[child], i); j++) {
                dp[root][i] = min(dp[root][i], dp[root][i - j] + dp[child][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    cin.ignore();
    for (int i = 1; i <= N; i++) {
        string line;
        getline(cin, line);

        string country;
        int j = 0;
        for (; line[j] != ' '; j++)
            country.push_back(line[j]);
        nameToIdx[country] = i;
        childNames[0].push_back(country);

        j++;
        for (; line[j] != ' ' and line[j] != '\0'; j++) {
            conquestTime[i] *= 10;
            conquestTime[i] += line[j] - '0';
        }

        while (line[j] != '\0') {
            country.clear();
            j++;
            for (; line[j] != ' ' and line[j] != '\0'; j++)
                country.push_back(line[j]);
            childNames[i].push_back(country);
            isVassal[country] = true;
        }
    }

    for (string name : childNames[0]) {
        if (isVassal[name])
            continue;
        childs[0].push_back(nameToIdx[name]);
    }

    for (int i = 1; i <= N; i++) {
        for (string name : childNames[i])
            childs[i].push_back(nameToIdx[name]);
    }

    initSizeOfSubtree(0);
    fill(&dp[0][0], &dp[N + 1][N + 1], 1e9);
    initDP(0);

    int answer = dp[0][M];
    for (int i = M + 1; i <= N; i++)
        answer = min(answer, dp[0][i]);

    cout << answer;

    return 0;
}

') {
            country.clear();
            j++;
            for (; line[j] != ' ' and line[j] != '
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> nameToIdx = {
    pair("#root", 0)
};

int N, M;

vector<int> childs[222];
vector<string> childNames[222];
int conquestTime[222];
unordered_map<string, bool> isVassal;
int sz[222];
int dp[222][222];

void initSizeOfSubtree(int root) {
    sz[root] = 1;
    for (int child : childs[root]) {
        initSizeOfSubtree(child);
        sz[root] += sz[child];
    }
}

void initDP(int root) {
    for (int child : childs[root])
        initDP(child);

    dp[root][0] = 0;
    dp[root][sz[root]] = conquestTime[root];

    for (int child : childs[root]) {
        for (int i = sz[root]; i >= 1; i--) {
            for (int j = 1; j <= min(sz[child], i); j++) {
                dp[root][i] = min(dp[root][i], dp[root][i - j] + dp[child][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    cin.ignore();
    for (int i = 1; i <= N; i++) {
        string line;
        getline(cin, line);

        string country;
        int j = 0;
        for (; line[j] != ' '; j++)
            country.push_back(line[j]);
        nameToIdx[country] = i;
        childNames[0].push_back(country);

        j++;
        for (; line[j] != ' ' and line[j] != '\0'; j++) {
            conquestTime[i] *= 10;
            conquestTime[i] += line[j] - '0';
        }

        while (line[j] != '\0') {
            country.clear();
            j++;
            for (; line[j] != ' ' and line[j] != '\0'; j++)
                country.push_back(line[j]);
            childNames[i].push_back(country);
            isVassal[country] = true;
        }
    }

    for (string name : childNames[0]) {
        if (isVassal[name])
            continue;
        childs[0].push_back(nameToIdx[name]);
    }

    for (int i = 1; i <= N; i++) {
        for (string name : childNames[i])
            childs[i].push_back(nameToIdx[name]);
    }

    initSizeOfSubtree(0);
    fill(&dp[0][0], &dp[N + 1][N + 1], 1e9);
    initDP(0);

    int answer = dp[0][M];
    for (int i = M + 1; i <= N; i++)
        answer = min(answer, dp[0][i]);

    cout << answer;

    return 0;
}

'; j++)
                country.push_back(line[j]);
            childNames[i].push_back(country);
            isVassal[country] = true;
        }
    }

    for (string name : childNames[0]) {
        if (isVassal[name])
            continue;
        childs[0].push_back(nameToIdx[name]);
    }

    for (int i = 1; i <= N; i++) {
        for (string name : childNames[i])
            childs[i].push_back(nameToIdx[name]);
    }

    initSizeOfSubtree(0);
    fill(&dp[0][0], &dp[N + 1][N + 1], 1e9);
    initDP(0);

    int answer = dp[0][M];
    for (int i = M + 1; i <= N; i++)
        answer = min(answer, dp[0][i]);

    cout << answer;

    return 0;
}

백준 1228번: 전쟁 [C++]