[2056] 작업 - 위상정렬, DP ★★☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/2056

2056번: 작업

 

---

[ 문제 접근 ]

- 위상정렬 문제 + 시간 계산

일단 기본 위상정렬과 다르지 않다. 코드 중간에 시간 계산을 위한 로직을 넣어줘야한다.

---

[ 최종 코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using std::cout; using std::cin;
using std::vector; using std::pair;


int n; // 작업 수
int time[10001];
vector<int> work[10001];
int indegree[10001];
int dp[10001];

void tS() {
	std::queue<int> q;

	for (int i = 1; i <= n; i++) { // 모든 작업을 돌면서 indegree가 없는 작업 q에 푸쉬.
		if (indegree[i] == 0) {
			q.push(i);
			dp[i] = time[i];
		}
	}
	while(!q.empty()) { 
		int cur = q.front();
		
		q.pop();
		for (auto elem : work[cur]) {
			dp[elem] = std::max(dp[elem], dp[cur] + time[elem]);
			if (--indegree[elem] == 0) {
				q.push(elem);
               // if 문 안에다가 dp 계산을 집어넣으면 반례 같은 상황이 나온다.
			}
		}
	}
	cout << *std::max_element(dp, dp + n+1);
}

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

	cin >> n;
	int x;

	for(int i=1;i<=n;i++){
		cin >> time[i] >> indegree[i];
		for (int j = 0; j < indegree[i]; j++) {
			cin >> x;
			work[x].push_back(i);	
		}
	}
	tS();
	return 0;
}

---

[ Key Point ]

 

👉 처음에는 DP 할 생각을 못하고 시간만 잡아 먹다가, 다른 분들의 블로그를 참조하여 풀었다.

 

아래는 내가 처음 한 틀린 방법이다.

while(!q.empty()) {  // for문으로 0 ~ n까지 해도 된다. 어짜피 한 루프당 한 작업이 되기 때문에.
		int cur = q.front();
		
		q.pop();
		for (auto elem : work[cur]) {
			if (--indegree[elem] == 0) {
				q.push(elem);
                time[elem] += time[cur];
			} 
		}
	}
	cout << *std::max_element(time, time + n+1);

 

처음에는 왜 이게 정답이 아닐까 계속 고민했다.

어짜피 그 전 소요시간에서 현재 작업의 소요시간을 더해주고 time 배열 가장 큰 값이 정답이 아닐까 고민했다.

 

그러다 백준에서 반례를 찾았다.

 

3
100 0
10 0
5 2 1 2

 

위에 보이는 첫번째 막대기? 가 문제에서 예시로 나온 케이스이다. 

이 경우 내 풀이로도 정답이 나온다.

 

하지만 아래 두번째 막대기를 보자.

5의 소요시간이 드는 3이라는 작업은 1과 2과 끝나야만 실행 될 수 있다고 해보자.

이 경우, 3이 1번 뒤에 붙는다는 보장이 없다.

if (--indegree[elem] == 0) {
    	q.push(elem);
}

이 부분이 q에 다음 작업을 넣는 로직인데, cur가 1번 작업일때 elem으로 3번 작업이라면, indegree[3]이 0이 아니기 때문에 q에 집어넣지지 않고 cur가 2번 일때 indegree[3]이 0이 되어 넣어지는것이다.

 

그래서 정답은 105가 나와야 되는 정답이 잘못된 코드로 하면 100이 나온는것이다.

 

 

핵심은 이거다.

 

예를들어 3번 작업이 1, 2번 작업을 선행 관계로 가지고 1번 작업이 10초, 2번 작업이 12초에 끝난다면 12초부터 3번 작업을 시작하면 된다는 뜻이다. 따라서 벡터를 통해 각 작업의 선행 작업을 저장한 후, 앞의 작업중에 가장 늦게끝나는 작업 시간을 가져오면 된다. 

 

이 앞의 작업 중 가장 늦게 끝나는 작업 시간을 가져오는걸 DP로 해결해야되는 문제였다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://dev-mb.tistory.com/256

ref :: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jhc9639&logNo=221551720536