[백준/BOJ] 백준 16468번 : 크리스마스 트리 꾸미기

https://www.acmicpc.net/problem/16468 16468번: 크리스마스 트리 꾸미기 이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에 www.acmicpc.net cache[트리높이][볼 개수]에 해당 트리높이에서 해당 볼 개수를 가지고 있을 때 만들어질 수 있는 트리의 경우의 수를 저장하는 방법으로, 트리에서 다이나믹 프로그래밍(트리 DP)을 이용해 문제를 해결했다. height높이의 트리를 ball_cnt개의 공으로 만드는 경우의 수를 구할때, 왼쪽 자식의 트리 또는 오른쪽 자식의 트리 중 최소 하나는 height - 1 높이의 트리를 ..

2023.03.14