이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다. 이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다. Square-order tree DP? 사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다. 트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다. 만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하..

문제 링크 질문은 언제나 환영입니다. 3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요! 두 가지 풀이법은 $O(n^3)$짜리 풀이이고, 한 가지 풀이법은 $O(n^2)$짜리입니다. 풀이 더보기 문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다. 세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다. 3차원 동적 계획법 $B(x,y,z):=x$개의 빌딩 중 왼쪽에서 $y$개, 오른쪽에서 $z$개만 보이는 경우의 수 위와 같이 정의하는 것은 아주 자연스럽습니다. 점화식을 도출할 때는 $B(x-1,\cdots )$와의 관계를 우선 생각 해봅시다. 새로 생긴 가장 긴 막대기를 어디다..