728x90
반응형
https://www.acmicpc.net/problem/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
반응형
'Algorithm > Beakjoon' 카테고리의 다른 글
[백준/Baekjoon] 4779 칸토어 집합 C++ :: Recursion & Divide and conquer (0) | 2023.11.04 |
---|---|
[백준/Baekjoon] 11725 트리의 부모 찾기 C++ :: Recursion & Graph (0) | 2023.11.04 |
[백준/Baekjoon] 16987 계란으로 계란치기 C++ :: Brute force & Back tracking (0) | 2023.11.02 |
[백준/Baekjoon] 1431 시리얼 번호 C++ :: Sort & compare func (0) | 2023.11.01 |
[백준/Baekjoon] 11652 카드 C++ :: Data structure (0) | 2023.11.01 |