코드 복사/붙여넣기 하는 당신이 아름답습니다.

16169 : 수행 시간

풀이

위상정렬

acm craft인가 그 문제랑 똑같은 것 같다. (사실 기억 안 남 ㅎ)

잘 짜주면 된다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, dap, l[101], t[101], d[101], r[101];
struct edg { int idx, dst; };
vector<edg> gph[101];

void go(int now) {
    dap = max(dap, r[now]);
    for (edg nxt : gph[now]) {
        r[nxt.idx] = max(r[nxt.idx], r[now] + t[nxt.idx] + nxt.dst);
        if (!(--d[nxt.idx])) go(nxt.idx);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &l[i], &t[i]);
        r[i] = t[i];
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        if (l[i]+1 == l[j]) {
            gph[i].push_back({ j,(i-j)*(i-j) });
            d[j]++;
        }
    }

    for (int i = 1; i <= n; i++) if (!d[i]) go(i);
    printf("%d\n", dap);
    
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-10-01 09:48

Read more posts by this author