jh1125kr   2달 전

이 문제를 결론적으로 말하면 dfs+dp로 해서 맞았긴했는데,

dfs로만 풀었던 방법이 시간초과도 아니고 틀렸습니다가 나와서 의문입니다.

일단 아래처럼 dfs+dp로 풀어서 맞았고

int dfs(int cur) {
    int cur_size = adj[cur].size();
    int &ret = dp[cur];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < cur_size; i++) {
        int next_v = adj[cur][i];
        ret = max(dfs(next_v), ret);
    }
    return ret = dp[cur] + building[cur];
}

dp를 적용하지 않았던 방법으로는 소스코드 처럼 풀었는데요...

시간초과나 스택오버플로우인 런타임에러는 이해가지만

왜 틀렸는지는 모르겠습니다..ㅠㅠ

jh1125kr   1달 전

해결했습니다.

1

10 11
10 1 1 100 10 10 100 1 1 1
1 2
2 3
3 6
4 3
4 7
4 9
5 4
6 9
7 8
8 9
10 7
9

이케이스에서 잘못된 값이 나왔습니다

댓글을 작성하려면 로그인해야 합니다.