[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 범위인 것도 확인하자.

정답 코드