반응형
SMALL
25515번 트리노드 합의 최댓값
-
백준 25515번 트리 노드 합의 최대값알고리즘 2023. 4. 3. 10:34
문제 설명 이번 문제는 트리가 주어지고 노드마다 하나의 정수가 적혀있을 때, 루트 노드에서 시작해 이웃한 노드를 방문하여 방문한 노드에 적혀있는 정수 합의 최대값을 출력하는 문제입니다. 문제 풀이 아이디어 각 노드에서 연결된 서브 트리에서의 최대값 찾기 루트 노드로부터 트리의 형태가 주어졌으므로, 루트노드와 연결된 각 서브트리에서 노드의 정수값을 더했을 때의 최대값을 구해줍니다. 한 노드에서 자신의 자식으로부터 얻어진 정수의 최대값을 알면 해당 서브트리에서 정수 합의 최대값을 구할 수 있습니다. 그러므로, 각 노드마다 자식으로부터 얻어진 정수합의 최대값과 자신의 정수값과의 합이 최대가되도록 해줍니다. 풀이 서브트리 정수합의 최대값 구하기 재귀를 이용하여 각 노드의 자식 노드를 탐색합니다. 각 노드가 le..