[백준] 12888 완벽 이진 트리 도로 네트워크

트리를 높이 그리면 규칙을 찾을 수 있다

테두리를 쭉~ 제일크게 1개로 감싸보자

그럼 안쪽에는 [나의 높이-2]*2 개가 필요하다는 것을 알 수 있다

물론 높이가 2 이상일 때 부터

그리고 그 다음에는 1 + 이전에 필요했던것 + [나의 높이-2]*2 개

이런 식으로 계속 간다!

미리 60까지 구해두자!

소스코드

#include <iostream>
using namespace std;
#define ll long long
ll d[66];
int main() {
    int n; scanf(" %d", &n);
    d[0] = d[1] = 1; d[2] = 3;
    ll sum = d[0] * 2;
    for (int i = 3; i <= 60; i++) {
        d[i] = 1+ sum + d[i - 2] * 2;
        sum += d[i - 2] * 2;
    }
    printf("%lld\n", d[n]);
}