[백준] 12888번 : 포화 이진 트리 도로 네트워크

문제

 

접근 방식

처음에는 이름이랑 그림만 보고 트리 문제인가 했는데 읽고서 그림을 그려보다 보니 DP 문제에 가까워 보였다.

 

근데 막상 DP를 사용해서 풀지도 않았고 이게 왜 티어를 골드 4까지나 준건지 모르겠는 문제인데, 규칙만 찾으면 코드 몇 줄로도 간단하게 풀 수 있다.

 

아래에서부터 왼중오 3개의 노드를 하나의 차로 방문하는 것이 가장 적은 차를 사용하는 경우이고, 주어진 입력내 트리의 노드 수가 long의 범위를 벗어나지 않기 때문에 DP를 사용하지 않고도 단순 연산으로도 풀 수 있다.

 

풀이

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 road = (2L << h) - 1;

		long result = road % 3 != 0 ? road / 3 + 1 : road / 3;

		System.out.println(result);
	}
}