[백준/Baekjoon] 2056 작업 C++ :: Dynamic Programming

https://www.acmicpc.net/problem/2056

2056번: 작업

---

1. Logic

처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다.

 

내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;
int tasktime[10001];
int done[10001];
vector<int> graph[10001];
int dp[10001];

int solve(int cur) {
    int &ret = dp[cur];
    if (ret != -1)
        return ret;

    if (graph[cur].size() == 0) {
        done[cur] = 1;
        return ret = tasktime[cur];
    }

    for (auto& next : graph[cur]) {
        ret = max(ret, solve(next) + tasktime[cur]);
    }

    done[cur] = 1;
    return ret;
}

int main() {
    cin >> n;
    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        int cost, cur;
        cin >> cost >> cur;

        tasktime[i] = cost;

        for (int j = 0; j < cur; j++) {
            int d;
            cin >> d;
            graph[d].push_back(i);
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        if (!done[i]) ans = max(ans, solve(i));
    }

    cout << ans;
}

 

 

---

3. Feedback

이 문제를 처음보고 위상정렬로 푸는 줄 알았는데 DP여서 완전히 감을 잘못 잡았다.. 위상 정렬은 보통 순서를 출력하라고 하는데 얘는 최단 거리를 출력하라고 했다. 이 점을 보고 위상정렬이 아닌 다른 알고리즘을 사용해야 한다는 것을 유추해볼 수도 있을 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90