트리에서의 다이나믹 프로그래밍

기본적인 dp 문제에서 관점과 새로운 사고를 할 상황들이 많아지는 알고리즘인 것 같다.

 

수학적 개념이 부족하여 dp의 점화식과 일반항 도출이 어려웠는데 

 

트리 dp에서도 비슷한 한계를 느낀다.

 

하지만 새로운 방법론과 사고 방법은 다른 알고리즘보다 재미있다.

 

관점과 다른 시각으로 트리를 보고 이용해야 한다는 점에서 더욱이 그렇다.

 

중등부 정 올 트리 dp 문제가 그러하다.

 

문제 자체에서는 o(n^2) 도 부분 점수를 보장하지만 

 

만점을 받기 위해서는 특정한 규칙을 찾아야 한다는 흐름이 좋았다.

 

간선의 관점, 노드의 관점, 루트와 서브 트리의 관계 등등 생각이 많아지지만 

 

이런 문제을 즐기게 된 게 얼마만인가.

 

노오오력! 

 

next level