색깔 하노이 탑 (Colored Hanoi) 1초 1024MB
문제
하노이 탑 게임은 3개의 기둥과 여러 장의 크기가 모두 다른 원판을 이용한 게임이다. 처음에는 1번째 기둥에 크기가 큰 원판이 밑에 오도록 모든 원판이 크기 순서대로 놓여 있고, 다음 규칙을 지키면서 모든 원판을 3번째 기둥으로 옮겨야 한다.
작은 원판 위에 큰 원판이 올라올 수 없다.
한 번에 1개의 원판만 옮길 수 있다.
이 규칙을 토대로 원판의 색깔이 두 개인 하노이 탑 게임을 만들려고 한다.
처음에는 1번째 기둥에 크기 1인 빨간 원판, 크기 1인 검은 원판, 크기 2인 빨간 원판, 크기 2인 검은 원판, …, 크기 N인 빨간 원판, 크기 N인 검은 원판이 위에서부터 차례대로 놓여 있다.
위의 규칙을 지키면서 원판을 움직여 3번째 기둥에 크기 1인 빨간 원판, 크기 1인 검은 원판, 크기 2인 빨간 원판, 크기 2인 검은 원판, …, 크기 N인 빨간 원판, 크기 N인 검은 원판이 위에서부터 차례대로 오도록 놓아야 한다면, 원판을 최소로 이동시킬 때 총 몇 번 이동해야 할까?
입력
첫 번째 줄에 정수 N (1 ≤ N ≤ 106)이 주어진다.
출력
첫 번째 줄에 원판의 최소 이동 횟수를 출력하여라. 수가 커질 수도 있으니, 최소 이동 횟수를 109 + 7로 나눈 나머지를 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 9점 | N ≤ 30 |
| #2 | 13점 | N ≤ 60 |
| #3 | 78점 | 추가 제한 없음 |
예제
1
3
로그인해야 코드를 작성할 수 있어요.