사용자 도구

사이트 도구


ps:problems:boj:1135

뉴스 전하기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1135
문제명뉴스 전하기
레벨골드 1
분류

트리 DP

시간복잡도O(nlogn)
인풋사이즈50
사용한 언어Python
제출기록33928KB / 164ms
최고기록56ms
해결날짜2021/11/03

풀이

  • 트리 DP문제.
  • 어떤 노드에서 차일드들에게 뉴스를 전달할때, 전달시간이 오래걸리는 서브트리에 먼저 전달하는 것이 가장 효율적인 방법이다.
  • 서브트리에 대한 DP값을, 서브트리의 루트에서 모든 노드로 뉴스를 전달하는 최소 시간으로 정의한다면, DP[0] > DP[1] > DP[2] > .. 으로 정렬되어있을때 DP[root] = max(i + DP[i])가 된다.
  • DP값을 한번 갱신할때마다, 정렬을 포함해서 O(|child| * log|child|)가 걸리므로, 총 시간복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 1135. 뉴스 전하기".

- Problem link: https://www.acmicpc.net/problem/1135
- Solution link: http://www.teferi.net/ps/problems/boj/1135

Tags: [DP] [DP on Tree]
"""

from teflib import ttree

ROOT = 0


def calc_dp(subtree_vals, _):
    subtree_vals.sort(reverse=True)
    return max((t1 + t2 for t1, t2 in enumerate(subtree_vals, 1)), default=0)


def main():
    N = int(input())
    parents = [int(x) for x in input().split()]
    tree = [[] for _ in range(N)]
    for u, par in enumerate(parents):
        if par != -1:
            tree[u].append(par)
            tree[par].append(u)

    print(ttree.dp_on_tree(tree, calc_dp, ROOT))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
C᠎ O I L O
 
ps/problems/boj/1135.txt · 마지막으로 수정됨: 2021/11/05 17:21 저자 teferi