둔필승총

하노이 탑 

www.acmicpc.net/problem/1914

문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

예제 입력 1

3

예제 출력 1

7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

[문제 해설]

막대가 3개가 있을때 생각해보자. 맨 밑에 젤 큰 원판 말고 나머지를 두번째 막대에 옮기고, 젤 큰 원판을 3번째 막대로 옮긴 뒤에, 두번째 막대에 있는 원판들을 3번째 막대로 옮기면 된다. 이걸 재귀 함수를 사용해서 풀면 된다.

mid_peg=(6-start_peg-end_peg) 인 이유 1,2,3 세 개니까 다 더하면 6임. 거기서 start_peg랑 end_peg를 빼면 나머지가 나옴. 거기로 옮겨야됨.

재귀함수에는 recursive case와 base case가 있다.

1. 원판이 없을때에는 아무것도 안해도 게임이 끝남( base case )

def hanoi(num_disks,start_peg,end_peg):
	if num_disks==0:
    	return

2. 원판이 하나 있을 경우에는 1번 기둥에서 3번 기둥으로 옮기면 끝난다. ( base case )

3. 원판이 2개인 경우에는 1번 원판을 1번 기둥에서 2번 기둥으로 옮기고, 2번 원판을 1번기둥에서 3번기둥으로 옮기고 1번 원판을 2번 기둥에서 3번 기둥으로 옮기면 된다.

4. 3번을 생각하면 recursive case에 관해서도 구할 수 있다.

def move_check(start,end):
    print(start,end)

def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)

일단 move_check(start,end) 함수는 start에서 end로 가는 것을 출력해 주는 함수라고 생각하면 된다.

그 다음 hanoi(move,start,end) 함수를 보자. 이 함수를 만든 것은 move를 start에서 end로 옮긴다고 생각하면 된다.

other은 start와 end가 아닌 나머지 기둥의 숫자이다. 1,2,3 세 개의 기둥이 있으므로 1 +2 + 3 = 6이다.

6에서 start와 end를 빼주면 other이 나올 것이다.

일단 맨 밑의 기둥 빼고 나머지를 other기둥에 두고 맨 밑에 탑을 end에 두고 other기둥에 있는 것을 end에 두면 된다.

이게 순서대로

hanoi(move-1,start,other)
move_check(start,end)
hanoi(move-1,other,end)

이렇게 되는 것이다. move_check로 하나하나 출력할 수 있다.

!!이 문제를 풀 때 주의할 점

1. 총 옮겨야 되는 것을 먼저 출력해 주어야 된다. 총 수를 구할려면 규칙을 찾으면 된다.

  탑이 하나일 때는 1번, 두 개일 때는 3번, 세 개일때는 7번... 규칙을 찾으면 sum*2+1을 하면 된다는 것이 보인다.

  이것을 먼저 출력해주자.

sum=0
for i in range(n):
    sum=sum*2+1

2. 이 문제에서 출력 초과가 계속 난다면 n이 20이 넘을때 과정을 생략해도 된다는 문제 설명을 읽었는지 확인하자!!

(나도 이것때매 문제를 계속 다시 보았다)

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)

[정답]

n = int(input())
k=0
def move_check(start,end):
    print(start,end)
def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)
sum=0
for i in range(n):
    sum=sum*2+1

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)