πŸ€–/λ°±μ€€

λ°±μ€€ 11729: ν•˜λ…Έμ΄ 탑 이동 μˆœμ„œ (Python)

sssbin 2021. 9. 8. 14:05

https://www.acmicpc.net/problem/11729

 

11729번: ν•˜λ…Έμ΄ 탑 이동 μˆœμ„œ

μ„Έ 개의 μž₯λŒ€κ°€ 있고 첫 번째 μž₯λŒ€μ—λŠ” 반경이 μ„œλ‘œ λ‹€λ₯Έ n개의 μ›νŒμ΄ μŒ“μ—¬ μžˆλ‹€. 각 μ›νŒμ€ 반경이 큰 μˆœμ„œλŒ€λ‘œ μŒ“μ—¬μžˆλ‹€. 이제 μˆ˜λ„μŠΉλ“€μ΄ λ‹€μŒ κ·œμΉ™μ— 따라 첫 번째 μž₯λŒ€μ—μ„œ μ„Έ 번째 μž₯λŒ€λ‘œ

www.acmicpc.net

 

def hanoi(n, a, b, c, list):
    if n == 1:
        list.append(f'{a} {b}')
    else:
        hanoi(n-1, a, c, b, list)
        list.append(f'{a} {b}')
        hanoi(n-1, c, b, a, list)

n = int(input())
list = []
hanoi(n, 1, 3, 2, list)

print(len(list))

for i in list:
    print(i)

 

a: from

b: to

c: by

 

1. μ›λ°˜μ΄ n개일 λ•Œ μž‘μ€ μ›λ°˜ n-1개λ₯Ό 1μ—μ„œ 2둜 이동

2. 큰 μ›λ°˜ 1개λ₯Ό 1μ—μ„œ 3으둜 이동

3. μž‘μ€ μ›λ°˜ n-1개λ₯Ό 2μ—μ„œ 3으둜 이동