백준 11829번 파이썬

1. 문제

2. 설명

알고리즘) 

n개의 원판이 있을때, n - 1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을 1번에서 2번으로 옮긴다. 

-> hanoi(n-1, a, c, b)

맨 밑의 원판을 1번에서 3번으로 옮긴다.

-> print(a, c)

그리고 n - 1개의 원판들을 다시 2번에서 3번으로 옮긴다.

-> hanoi(n-1, b, a, c)

 

최소한의 이동 값 규칙)

n = 1일 때 1, n = 2일 때 3, n = 3일 때 7, n=4일 때 15 이므로 (2^n - 1)이라는 식이 나온다.

3. 코드

n = int(input())
def hanoi(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        hanoi(n-1, a, c, b)
        print(a, c)
        hanoi(n-1, b, a, c)
sum = 2 ** n - 1
print(sum)

hanoi(n, 1, 2, 3)

---

하노이탑.. 대학생 때 분명 본 문제 같은데 풀이 방법 자체가 가물가물했다.

문제를 봤을 때 좋은 알고리즘이 생각나지 않았다.. 내 머리... 좀 더 수학적으로 핑핑 돌아갈 수는 없겠니?

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

이 분의 블로그에 하노이탑의 알고리즘이 아주 자세히 설명되어있다.

다행히 한번에 보고 알고리즘이 이해됐다.

만약 해당 블로그를 안봤더라면 하루 종일 봐도 못 풀었을 것이다.

훗날 백준 복기할 때에는 안보고도 잘 풀 수 있길...

1일 1알고리즘 화이팅!