12888번: 완전 이진 트리 도로 네트워크

문제 설명

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

12888번: 완전 이진 트리 도로 네트워크

[문제]

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

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

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

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

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

 

[입력]

 첫째 줄에 H이 주어진다. (0 ≤ H ≤ 60)

 

[출력]

 모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차를 최소 몇 대를 보내야 하는지 출력한다.

정답은 항상 64비트 정수로 나타낼 수 있다.

 

[예제 입력 1]

1

[예제 출력 1]

1

[예제 입력 2]

2

[예제 출력 2]

3

---

풀이

 이 문제 해결에 대한 아이디어는 트리 구조에서 나왔다. 일반적인 트리 구조라 하면 부모 노드보다 단말 노드의 수가 많다.

 위와 같은 완전 이진 트리 구조에서, 만약 한쪽의 단말 노드가 경로를 그리며 부모 노드를 경로에 포함하면, 다른 단말 노드 한 쪽은 자신의 하위 노드로 내려가는 경로가 아니라면 경로를 그릴 수가 없다. 결국 이렇게 강제적으로 네트워크가 단절되는 상황에서, 또 다른 완전 이진 트리 네트워크가 생겨나는 것이다. 그렇다면 이런 하위 완전 이진 트리 네트워크의 경우 해당 레벨 크기 정도에서의 최적의 답이 존재한다.

 이렇게 네트워크를 분할하면서 최적의 답을 찾으려면 우선 가장 효과적으로 많은 노드를 지나는 경로가 필요한데, 이런 경로가 바로 가장 왼쪽의 리프 노드에서 가장 오른쪽의 리프 노드로 가는 경로이다. 이렇게 되면 둘 간의 최소 공통 조상 노드가 루트 노드기 때문에 가장 많은 노드를 지나게 된다. 이 경로를 제외하고 남은 노드들을 보면 기존 트리의 레벨을 H라 할 때 레벨이 0부터 H - 2 인 트리 네트워크가 2개씩 존재한다. 또한 그런 세부 네트워크의 최적의 답은 재귀호출을 통해 구하면 된다.

 

#include <iostream>

using namespace std;
long long cache[61] = { 0, }; //동적 프로그래밍용 캐시

long long search(int H) { //재귀호출 기반 탐색
	long long result = 0;

	if (cache[H] != 0) //캐시 값 반환
		return cache[H];

	for (int i = 0; i <= H - 2; i++)
		result += search(i);

	return cache[H] = 1 + 2 * result;
}

int main() {
	int H;
	long long answer;

	cin >> H;
	//트리 레벨이 0, 1인 경우 한 가지
	cache[0] = 1;
	cache[1] = 1;

	answer = search(H);

	cout << answer;

	return 0;
}

---

결과