BOJ::2056 작업

[BOJ] : https://www.acmicpc.net/problem/2056

시사점

// 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)

좋은 코드

최적화