백준 1005 ACM Craft

작성일 | In |

Problem : ACM Craft

유형 : 위상정렬, DP

문제 해석

  • N번쨰 건물을 짓는 최소 시간을 구하라.

문제 재해석

  • 건물을 못 짓는 경우는 없다.
  • 앞 테크의 건물을 전부 지어야 뒤 테크의 전물을 지을 수 있다.

해결 전략

  • 순서를 유지한 정렬이 필요하다 위상 정렬로 해결한다.
  • 최소 건설 시간을 찾아야 한다. DP로 해결한다.

설계, 구현

  • 각 건물당 짓는 비용을 저장해둔다.
  • 테크가 필요 없는 건물부터 건물을 짓기 시작한다.
  • 새로운 건물을 지을 때, 현재 테크까지 올린 비용 + 새로운 건물 비용을 구한다.
  • 새로운 방법으로 짓는 건물이 더 쌀 경우 해당 방법으로 교체한다.

디버깅

  • 문제를 잘못 읽었었다.
  • 앞 테크의 건물을 모두 지어야 뒷 테크의 건물을 지을 수 있다.
  • 하지만, 한 개만 지어도 지을 수 있는 것으로 잘못 해석했었다.

코드

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
#include <bits/stdc++.h>
using namespace std;

int n, k, t;
int fin;

vector<int> node[1002];
int build_cost[1002], build_dp[1002], build_indegree[1002];


void Solve() {
    queue<int> q;

    for (int i = 1; i <= n; ++i) {
        if (build_indegree[i] == 0) {
            q.push(i);
            build_dp[i] = build_cost[i];
        }
    }

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (const auto& nxt : node[cur]) {
            build_dp[nxt] = max(build_dp[nxt], build_dp[cur] + build_cost[nxt]);
            build_indegree[nxt]--;
            if (build_indegree[nxt] == 0) q.push(nxt);
        }
    }
    cout << build_dp[fin] << "\n";
}

void Input_Build_Order() {
    int a, b;
    for (int i = 0; i < k; ++i) {
        cin >> a >> b;
        node[a].push_back(b);
        build_indegree[b]++;
    }
}

void Input_Build_Cost(){
    for (int i = 1; i <= n; ++i) {
        cin >> build_cost[i];
    }
}

void Init() {
    memset(build_cost, 0, sizeof(build_cost));
    memset(build_indegree, 0, sizeof(build_indegree));
    memset(build_dp, 0, sizeof(build_dp));
    for (int i = 1; i <= n; ++i) {
        node[i].clear();
    }
}

void Input() {
    cin >> t;
    while (t--) {
        Init();
        cin >> n >> k;
        Input_Build_Cost();
        Input_Build_Order();
        cin >> fin;
        Solve();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();

    return 0;
}

피드백

  • 항상 문제를 똑바로 읽자.