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

문제 링크

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

간단해 보이니까 머리를 싸매고 잘 생각해보자..

어... 음...

헷갈린다.

이럴땐 그림판으로 그림을 그려보면 된다.

와! 규칙을 찾았다!

$i$가 홀수일 때 $d[i] = (d[i-1] - 1)*2 + 1 = d[i-1]*2 - 1$

$i$가 짝수일 때 $d[i] = d[i-1]*2 + 1$

그대로 코드로 옮기면 된다.

단, $0 \leq n$이므로 $n = 0$인 경우도 구해줘야 한다. 

답이 나올 수 있는 범위는 long long 범위인 것도 확인하자.

정답 코드

	#include <iostream>
	using namespace std;
	int n;
	long long d[63] = { 1, 1};
	int main() {
	cin >> n;
	for (int i = 2; i <= n; i++) {
	if (i & 1) {
	d[i] = d[i - 1] * 2 - 1;
	}
	else {
	d[i] = d[i - 1] * 2 + 1;
	}
	}
	cout << d[n];
	}

view raw 12888.cpp hosted with ❤ by GitHub