문제
https://www.acmicpc.net/problem/1914
Algorithm
재귀호출을 이용해서 풀었다.
이동횟수는 항상 2**n-1
1 1번 기둥에 N개 원판 있고,이를 3번 기둥으로 옮길때
2 1번 기둥에 위치한 N개의 원판 중 N-1 개를 2번으로 옮김
3 나머지 1개를 3번으로 옮김
4 2번 기둥에 있는 N-1개 원판을 3번 기둥으로 옮김
f(n,a,b,c): n개 원판 1번기둥 a, 2번기둥 b, 3번기둥 c
n=1이면 하나 옮기면 끝
n>1이면
1 1번의 N-1개를 2번으로 옮겨야 하므로 f(n-1,a,c,b)
2 나머지 1번의 1개를 3번으로 옮겨야 하므로 f(1,a,b,c)
2번 기둥에 잇는 n-1개를 3번으로 옮겨야 하므로 f(n-1,b,a,c)
Code
def f(n, a, b, c):
if(n == 1):
print(a, c, sep = " ")
else:
f(n-1, a, c, b)
f(1, a, b, c)
f(n-1, b, a, c)
n = int(input())
print(2**n-1)
if(n <= 20):
f(n, 1, 2, 3)
'Koala - 10기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[ 백준 / Python ] #9663 N-Queen (1) | 2023.05.26 |
---|---|
[ 백준 / Python ] #5430 AC (0) | 2023.05.21 |
[ 백준 / Python ] #1515 수 이어 쓰기 (0) | 2023.05.19 |
[백준 / Python] # 2812번 크게 만들기 (0) | 2023.05.13 |
[백준 / Python] #1124 언더프라임 (0) | 2023.05.12 |