7283 : 재귀 하노이 횟수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 원판을 이동하는 하노이 탑의 최소 이동 횟수를 구하십시오.
점화식: $T(1) = 1$, $T(n) = 2T(n-1) + 1 = 2^n - 1$
$N$이 최대 60이므로 64비트 정수 범위를 초과할 수 있어 Big Integer가 필요합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
점화식: $T(1) = 1$, $T(n) = 2T(n-1) + 1 = 2^n - 1$
$N$이 최대 60이므로 64비트 정수 범위를 초과할 수 있어 Big Integer가 필요합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원판의 개수 $N$이 주어집니다. ($1 \le N \le 60$)
출력 설명
하노이 탑의 최소 이동 횟수 $2^N - 1$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
$2^N - 1$을 계산합니다. Python에서는 정수 크기 제한이 없으므로
2**N - 1로 직접 계산할 수 있습니다. $N=63$이면 약 $9.2 \times 10^{18}$입니다.