교대최소제곱법
[백준 파이썬 1914번 하노이 탑] 하노이 탑의 이해 본문
하노이탑 문제의 답은 2**N - 1 이다.
라고 외웠었는데 왜 그럴까?
하노이탑의 기본 원리는 N개를 2번 기둥으로 옮기고 가장 큰 원판을 3번 기둥으로 옮긴 뒤 다시 N개를 3번 기둥으로 옮기는 방식이다.
즉,
hanoi(n-1) + 1 + hanoi(n-1)그럼 이게 왜 2**N - 1 일까?
만약 3번의 재귀를 돌았을 때를 계산해보면 다음과 같다.
2(2(2(x + 1) + 1) + 1 = 8x + 4 + 2 + 1
결국 1 + 2 + 4 + 8 + ... = 2**N - 1 인 것이다.
1914번: 하노이 탑
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
'코딩테스트' 카테고리의 다른 글
| [2023 하반기 삼성 코테] 후기 및 분석 (1) | 2023.10.15 |
|---|---|
| [코테 준비] 라이브러리 없이 살아남기 (0) | 2023.10.14 |
| [백준 파이썬 2638번 치즈] 구현 최적화 (0) | 2023.10.09 |
| [백준 파이썬 14502번 연구소] 구현 최적화 (1) | 2023.10.09 |
| [백준 파이썬 12015번 가장 긴 증가하는 부분 수열 2] DP, Bisect (0) | 2023.10.05 |
'코딩테스트' Related Articles
more
