BOJ 24545 : Y

문제 링크 : https://www.acmicpc.net/problem/24545

 

전형적인 Tree DP 문제이다.

나는 D1, D2,  D 세 가지 다이나믹 배열을 정의하여 해결했다.

 

D1[i] := i 번 노드가 꼭대기인 단일 체인의 최대 길이

D2[i] := i 번 노드가 꼭대기인 Y 트리의 최대 크기 ( V 모양도 포함 )

D[i] := i 번 노드가 루트인 서브트리에서의 Y 트리의 최대 크기

D1[i] (빨간색) 과 D2[i] (파란색)

이제 DP 식만 잘 세워주면 된다.

D1[i] 는 ( 자식들의 D1 들 중 max 값 ) + 1 이다.

D2[i] 는 ( 자식들의 D2 들 중 max 값) + 1 과,  ( 자식들의 D1 들 중 큰 것 2개의 합 ) + 1 중 큰 값이다.

 

그럼 D[i]는 어떻게 하면 될까?

1. 서로 다른 두 자식들의 D1 + D2 들 중 max 값 + 1 ( 위 그림을 보면 쉽게 이해 된다 ) 

2. 자식들의 D2들 중 max 값 + 1

 

1, 2 번 값 중 더 큰 값을 선택하면 된다.

 

최종 정답은 D[1...N] 중 최댓값이다.