7302 : 하노이 최적 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 원판을 이동하는 하노이 탑의 최소 이동 횟수를 구하십시오.
최소 이동 횟수는 점화식 $T(n) = 2T(n-1) + 1$에 의해 $2^N - 1$로 증명됩니다.
$N$이 최대 25이므로 값이 매우 커집니다. Big Integer 자료형을 사용해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
최소 이동 횟수는 점화식 $T(n) = 2T(n-1) + 1$에 의해 $2^N - 1$로 증명됩니다.
$N$이 최대 25이므로 값이 매우 커집니다. Big Integer 자료형을 사용해야 합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원판의 개수 $N$이 주어집니다. ($1 \le N \le 25$)
출력 설명
하노이 탑의 최소 이동 횟수 $2^N - 1$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
31도움
Python에서는 정수 크기 제한이 없으므로
2**N - 1로 직접 계산합니다. $N=25$이면 $2^{25}-1 = 33{,}554{,}431$입니다.