STUDY/Algorithm

[백준] 11729 하노이 탑 이동 순서

sinawi95 2021. 2. 14. 13:59
728x90

www.acmicpc.net/problem/11729

 

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

def hanoi(disk, start, mid, end):
    if disk == 1: #목적지로 옮기기 위해
        print(start, end)
    else:
        hanoi(disk - 1, start, end, mid)    # 2**(n-1)  n-1개를 mid에 옮김
        print(start, end)                   # 1         가장밑에있는 것을 end로 옮김
        hanoi(disk - 1, mid, start, end)    # 2**(n-1)  mid에 있는걸 다시 end로 옮김

n = int(input())
print(2**n - 1)
hanoi(n, 1, 2, 3)

총 이동 횟수는 쉽게 구했는데 중간에 이동하는 방법에서 해맸다.

방법은 알고있어도 어떻게 구현하는지가 핵심인데 아직 더 노력해야한다는 생각이 든다.

'STUDY > Algorithm' 카테고리의 다른 글

[SWEA] 1211. [S/W 문제해결 기본] 2일차 - Ladder2  (0) 2021.02.16
[백준] 2447 별찍기  (0) 2021.02.14
[백준] 1002 터렛  (0) 2021.02.12
[백준] 9020 골드바흐의 추측  (0) 2021.02.12
[백준] 4948 베르트랑 공준  (0) 2021.02.12