BOJ
BOJ::2056 작업
BOJ Gold 3
BOJ::2056 작업
[BOJ] : https://www.acmicpc.net/problem/2056
- Level : Gold 3
시사점
- 최소 시간을 출력해야 하는 문제인데, queue 처리 중 최대 값을 갖는 누적값으로 바꿔치기 하는 부분이 완벽히 이해되진 않았습니다.
- 이해된 내용을 업데이트 하겠습니다.
- 예제 testcase로 주어진 그래프를 손으로 그려보면 쉽게 이해가 될 수 있습니다.
- 규칙 : vertex i가 수행되기 위해서는, vertex i-1까지 모든 task가 완료되어야 합니다.
- 예를 들어, 예제와 같이
- 1번 작업 : 0~5, 2번 작업: 5~6
- 3번 작업 : 6~9, 4번 작업 : 5~11
- 5번 작업 : 11~12, 6번 작업 : 11~19
- 7번 작업 : 19~23
- 단순히 1번에서 시작해서 7번까지 빠른 경로만을 찾아서 가는 것이 아니라,
- 7 번에 연결된 3, 5, 6 을 모두 끝내야 7번에 도달할 수 있습니다.
- 즉, 7번까지 오는 경로 중 가장 오래 걸리는 시간 이후에 7번에 도달할 수 있습니다.
- 이와 같은 이유로, accumulation을 뜻하는 accut[there]는 항상 최대값(즉, 마지막 도달값)을 가지게 합니다.
// accut[there] = accut[here] + dt[there]; 왜 아래 코드처럼 더 큰 것을 넣어야 할까?
accut[there] = max(accut[there], accut[here] + dt[there]);
이해(5)
- 시사점 챕터에 이해를 충분히 도울만큼 설명하였습니다.
설계(5)
시간 복잡도
공간 복잡도
구현(20)
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 10000 + 1;
int n;
int dt[MAX_N];
int accut[MAX_N];
int indegree[MAX_N];
vector<int> adj[MAX_N];
priority_queue<int> pq; // index(low)
int solve(){
while(!pq.empty()){
int here = -pq.top(); pq.pop();
for(int i = 0; i < adj[here].size(); i++){
int there = adj[here][i];
// accut[there] = accut[here] + dt[there]; 왜 아래 코드처럼 더 큰 것을 넣어야 할까?
accut[there] = max(accut[there], accut[here] + dt[there]);
indegree[there]--;
if(indegree[there] == 0){
pq.push(-there);
}
}
}
int ret = 0;
for(int i = 1; i <= n; i++)
ret = max(ret, accut[i]);
return ret;
}
int main(){
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> dt[i];
int cnt;
cin >> cnt;
for(int j = 0; j < cnt; j++){
int prev;
cin >> prev;
if(prev == 0) continue;
adj[prev].push_back(i);
indegree[i]++;
}
}
for(int i = 1; i <= n; i++)
if(indegree[i] == 0){
pq.push(-i);
// 위상이 0인 지점의 누적 값을 미리 처리합니다.
accut[i] = dt[i];
}
cout << solve() << endl;
return 0;
}
디버깅(10)
- 구현 챕터에서 주석 처리 해 놓은 것 처럼, max를 취하는 부분을 빼먹고 구현하였습니다.