2022-10-29-#1914-하노이탑
[문제]
세개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. «< 매우 중요
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동횟수는 최소가 되어야 한다.
[입력]
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N(1≤N≤100)이 주어진다.
1
3
[출력]
첫째 줄에 옮긴 횟수 k를 출력한다.
N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 k개의 줄에 걸쳐 두 정수 A B를 빈칸 사이에 두고 출력하는데, 이는 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.
1
2
3
4
5
6
7
8
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
[풀이]
이쯤되면 감이 오기 시작하는게 ‘’’최소 턴의 개수’’’를 물어본다는 것은 재귀함수를 이용하라는 뜻으로 받아들이는 경지에 오름. (근데 여기까지임.)
- 문제를 푸는데에 있어 가장 먼저 생각해야 할 것 ! 어떤 방식으로 풀 것인가 ?
→ 재귀 함수 이용
- 그렇다면 파라미터로 무엇을 넣어줄 것인가? « 가장 어려움
→ n …
감이 안 온다 싶으면 예시를 더 찾아보자 !
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n1 = 1
1
1 3 # 0 0 1
n2 = 2
3
1 2 #1 1 0
1 3 #0 1 1
2 3 #0 0 2
n3 = 3
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
예시를 봐도 감이 안 오다보니 직접 코드를 작성해보면 맞춰나가는 형태로 풀었다..
[코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import numpy as np
n = int(input())
'''
2
2 0 0
1 1 0
0 1 1
0 0 2
'''
def hanoi(n, start, mid, end): #2, 1, 2, 3
if n == 1:
print(start, end, sep="") #1, 2,
'''
우리가 출력할 것은 (처음, 마지막) set만 !!
처음과 마지막에 지금 (어디에서(from),어디로(to))로만 저장해주면 되는 문제임 !!
'''
else:
hanoi(n - 1, start, end, mid) # 1->2 (첫번째에서 두번째로 옮김) => (start, mid)만 출력
hanoi(1, start, mid, end) #이전 상태를 출력 (이미 바뀌기 전에 !)
hanoi(n - 1, mid, start, end) #2->3
print(2**n - 1)
print(hanoi)
if(n<=20):
f(n, 1, 2, 3)
주석에 달려있는 것처럼 처음과 끝만 출력하면 되기 때문에 각각의 번호 위치를 바꿔주는 형태로 풀었다 !
소요 시간 대략 1시간.. 역시 어려움
📌things that you can get from this problem
- “””최소턴”””을 구하는 문제 ⇒ ‘재귀함수’문제 유형인지 의심하자
- 재귀함수라면 파라미터로 무엇을 받아야 하는지부터 고민 «< 여기까지만 해도 당신은 .. 천하를 호령한다는 뜻임 ..
- 마지막으로 ‘’’종료조건’’’ 생각 및 케이스가 나뉘는 문제라면 케이스 또한 생각하기 !