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

문제

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

BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다.

수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다.

아래 그림은 H = 2일 때, 그림이다.

수빈이는 도로 네트워크에 차를 보내려고 한다. 모든 차는 시작 도시와 도착 도시가 있으며, 같은 도시를 두 번 이상 방문하지 않는다. 차의 시작 도시와 도착 도시가 같을 수도 있다.

모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차를 최소 몇 대를 보내야 하는지 구하는 프로그램을 작성하시오.

풀이

[첫 번째 접근]

공식을 찾아서, 바로 계산해서 내보내는 방식으로 해보았다. 

몇 단계를 적어서 확인해보니 공식을 찾을 수 있었다. 

공식을 이용하면 O(logN)의 복잡도로 문제를 해결할 수 있었는데, 제출해보니 틀렸습니다가 나왔다.

공식에 오류가 있어서 그런거라고 생각하지만, 틀린 이유를 정확히는 모르겠다. 

 

[두 번째 시도] 

DP공식을 찾아서 DP방식으로 해보았다. 

코드

#include <iostream>

#define sc scanf_s //제출시엔 scanf로 바꿔야함
using namespace std;

long long dp[61];
int main() {
	int H; sc("%d", &H);
	dp[0] = 1; dp[1] = 1;
	for (int i = 2; i <= H; i++) { 
		if (i % 2 == 0) { //짝
			dp[i] = dp[i - 1] * 2 + 1; 
		}
		else { //홀
			dp[i] = dp[i - 1] * 2 - 1;
			
		}
	}
	printf("%lld\n",dp[H]);
}

결과