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

백준 12888 완전 이진 트리 도로 네트워크

• https://www.acmicpc.net/problem/12888

• 트리의 가장 외곽을 따라 리프 노드 ~ 리프 노드로 올라갔다 내려오는 방법이 최적의 방법이다

#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int H;
	cin >> H;

	//dp[h]: 높이가 h일 때 필요한 차의 개수
	ull dp[61];
	
	dp[0] = 1;
	dp[1] = 1;
	
	//현재 높이가 h일 때
	//높이가 0 일 때 필요한 차의 개수의 합 + ... + 높이가 h-2 일 때 필요한 차의 개수의 합
	ull psum = 1;

	for (int h = 2; h <= H; ++h) {
		dp[h] = 1 + (2 * psum);
		psum += dp[h - 1];
	}

	cout << dp[H];

	return 0;
}

📌참고자료

• 백준 12888 완전 이진 트리 도로 네트워크 풀이
  https://m.blog.naver.com/pasdfq/221314987317