반응형 공통 조상1 [C/C++] 백준 #1646 피이보나치 트리(동적 계획법) 피이보나치 트리 문제는 일견 어려워보일 수 있지만, 조성 방법이 정해져 있기 때문에, 그것을 이용해서 푸시면 됩니다. 정답자가 현재 90명정도로 적은 편의 문제입니다. 구현 자체가 어려워서라기보다는 문제 자체가 어려워서인 듯 합니다. N이 주어졌을 때, 루트는 최고층(가장 높은 레이어)에 위치하며 가장 먼 노드까지는 N-1번이면 도착하게 됩니다. 왼쪽 트리는 N-2에 대한 루트이고, 오른쪽 트리는 N-1에 대한 트리입니다. 이것을 이용하면 전체 트리에 대한 노드의 갯수 \(ft_N\)을 구할 수 있습니다. \[ ft_0 = 1, ~ ft_1 = 1 \] \[ ft_n = ft_{n-2} + ft_{n-1} + 1 \] 위의 점화식을 이용하면 우리는 손쉽게 노드의 갯수를 구할 수가 있습니다. 이제 이것을 .. 2022. 9. 18. 이전 1 다음 728x90
