[BOJ] 백준 12888번 완전 이진 트리 도로 네트워크 (Java)

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

난이도 : 골드 4

유형 : dp / 트리

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

▸ 문제

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

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

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

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

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

▸ 입력

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

 

▸ 출력

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

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

 

문제 풀이  

그래프 탐색인줄 알았으나 처음에 그냥 한 번 규칙 찾아보려고 그려보다가 바로 발견해버렸다. 트리 문제풀려고 들어왔는데 사실상 dp 점화식 문제였다...

 

h가 짝수 일 때는 1~h까지의 트리는 이전 트리의 중복임을 알 수 있다. 그러면 이미 최적의 해를 찾았다는 가정 하에 남은 노드들만 따져주면 된다. 그러면 다음과 같이 루트 노드가 홀로 남아있는 것을 볼 수 있다. 

• i%2 ==0, dp[i] = dp[i-1]*2 + 1

짝수 트리

 

h가 홀수 일 때도 마찬가지이다. 1~h까지의 트리는 이전 트리 중복이다. 그런데 다른 점이 있다. 짝수 트리에서 홀로 남았던 루트노드들이 새로운 짝이 생겼다. 그래서 양쪽의 루트노드를 -2 빼준 후 새로운 경로 + 1을 추가해주면 된다.

• i%2 ==1, dp[i] = dp[i-1]*2 - 2 + 1 =  dp[i-1]*2 - 1

 

홀수 트리

 

풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int h = Integer.parseInt(br.readLine());
		
		long[] dp = new long[61];
		dp[0] = dp[1] =1;
		for(int i=2; i<=h; i++) {
			if((i&1) == 1) { 
				dp[i] = dp[i-1]*2 -1;
			}else {
				dp[i] = dp[i-1]*2 +1;
			}
		}
		
		System.out.println(dp[h]);
	}
}