문해기 과제 4

과제 4: 레드-블랙 하노이탑

하노이탑은 모두가 잘 알고 있는 문제이다. a, b, c 3개의 원기둥이 있고, 서로 다른 크기의 n개의 구멍뚫린 원반이 a에 크기 순으로 놓여 있는데 이를 c로 다음 규칙을 지키면서 이동하면 된다. 

- 한번에 한개씩

- 작은 원반 위에 큰 원반 x 

이제 2n개의 구멍뚫린 원반을 이용하는 하노이탑을 생각해보자. 원반의 크기는 n가지로, 각 크기마다 빨간 원반, 까만 원반 둘이 있다. 처음 a기둥에는 원반이 크기순서대로 놓여 있는 것은 같지만, 같은 크기의 원반 둘은 빨간 원반이 까만 원반 위에 있다. 이제 하노이탑 규칙을 따르면서, c 기둥에 그대로 원반을 모두 옮기려고 한다. (크기 순서대로, 같은 크기는 빨간 원반이 까만 원반 위) 이 때 필요한 원반의 최소 이동회수를 구하고 이를 1,000,000,007로 나눈 나머지를 출력하는 프로그램을 작성하시오.

이동하는 과정에서는 같은 크기의 까만 원반이 빨간 원반 위에 올 수 있지만, 최종적으로는 빨간 원반이 까만 원반 위에 와야 한다. 

입력

표준 입력으로 입력을 받는다. 입력은 하나의 정수 N으로 1 이상 1,000,000 이하이다. 원반의 개수가 2*N개라는 뜻이다. 

출력 

표준 출력으로 출력한다. 출력은 하나의 정수로, 원반의 이동 횟수를 1,000,000,007로 나눈 나머지를 출력한다. 

 

힌트 

N이 1이면 출력이 3, 2면 출력이 11,  3이면 27,  4면  출력이 59, 5면 출력이 123이다. 

 

#include <iostream>
#include <cmath>
using namespace std;

typedef long long int lld;

int main(){ 
     ios_base::sync_with_stdio(NULL);
     cin.tie(NULL);
     cout.tie(NULL);
    lld n;
    cin>>n;

    lld a = pow(10,9)+7;
    lld ans = 1;
    for(lld i = 0; i < n+lld(2); i++){
        ans *= lld(2);
        ans %= a;
    }
    ans -= lld(5);
    cout<<ans;
    return 0;
}