https://www.acmicpc.net/problem/11729
문제 접근
언젠가 더 지니어스 이런곳에서 봤던 것 같은 하노이 탑 문제이다.
예제 입력 1 을 통해 문제를 우선 체득해보겠다.
예제 입력에 3이 입력되면 첫번째 장대에 3층짜리 탑이 있다는 뜻이다.
이를 세번 째 장대에 크기가 큰 원판부터 작은 원판 순으로 쌓아 올려야한다.
출력은 첫 째줄에 옮긴 시행 횟수가 출력되고, 그 이후로 시행 과정이 출력되어야 하는데
A B 식으로 공백을 두고 사이에 두 숫자가 오는데 이는 A번 장대에 탑을 B번 장대로 옮긴다는 뜻이다.
다시 예제를 보자.
3층짜리 탑이 1번 장대에 있고 이를 3번 장대로 옮기려고 한다.
1 3
ㅇㅇ ->
ㅇㅇㅇ ㅇ 1 2
->
ㅇㅇㅇ ㅇㅇ ㅇ 3 2
-> ㅇ
ㅇㅇㅇ ㅇㅇ 1 3
-> ㅇ
ㅇㅇ ㅇㅇㅇ2 1
->
ㅇ ㅇㅇ ㅇㅇㅇ2 3
-> ㅇㅇ
ㅇ ㅇㅇㅇ1 3
ㅇ
-> ㅇㅇ
ㅇㅇㅇ이 과정을 통해 예제가 진행된다.
음 아직 규칙을 모르겠다.
N=4 일때 과정을 봐야 알 것 같다.
ㅇ
ㅇㅇ
ㅇㅇㅇ
ㅇㅇㅇㅇ를 3번장대에 옮겨 보겠다.
어? 뭔가 보인다.
이는 3층짜리 탑을 2번 장대에 다 올리고 4칸짜리를 3번 장대에 깔고
3층짜리 탑을 다시 3번 장대에 올리면 된다.
다시 생각해보자
1. 3층짜리 탑을 2번 장대에 올린다. (N=3일때 알고리즘)
2. 4칸짜리를 3번장대에 깐다.
3. 2번장대에 올라간 3층짜리 탑을 3번 장대에 올린다 (N=3일때 알고리즘)
오케이 여기까지는 파악했다.
N이라면?
1. N-1층짜리 탑을 2번 장대에 올린다.
2. N칸짜리를 3번장대에 깐다.
3. 2번 장대에 올라간 N-1층 짜리 탑을 3번 장대에 올린다.
-> 이 방식은 결국 N-1개의 원판을 두번째 장대로 옮긴 다음, 가장 큰 원판을 목적지로 이동시키고, 다시 N-1개의 원판을 목적지로 옮기는 재귀적인 구조로 이해할 수 있다.
오케이.
코드로 이 논리를 변환해야 한다.
나는 세개의 장대중 탑이 있는 장대 'start'라 하고 옮기려는 목적지 장대를 'end' 라 하겠다. 그리고 나머지 이용하는 장대를 'sub'라 하겠다.
그렇다면 아까 N 이었을 때 논리는 이렇게 표현할 수 있다.
1. N-1층짜리 탑을 sub로 할당한다.
2. N칸짜리를 end에
3. sub에 올라간 N-1층 짜리 탑을 end 장대에 올린다.
이는 다음과 같이 코드로 표현가능하다.
def hanoi(N, start, end):
if N == 1:
print(start, end) # N이 1이라면 start에서 end로 옮겨버리면 끝.
return
sub = 6 - start - end # 1,2,3번 장대가 있기에 start+sub+end 는 6임을 이용하여 sub장대를 구할 수 있다.
hanoi(N - 1, start, sub) # N이 1이 아니라면 N-1을 start 에서 sub로 옮기겠다.
print(start, end) # start에 남은 맨 바닥 탑을 end로 보내고
hanoi(N - 1, sub, end) #그리고 sub에 있는 원판들을 end로 보내면 끝.
이제 시행횟수만 구하면 되는데
T(N) = T(N-1) + 1 + T(N-1) 의 구조를 띄고 있음을 우리는 이제 알고있다.
즉 T(N) = 2(N-1) +1 인데
T(1) =1 이기에
T(2) = 2(1) + 1 = 3 이고
T(3) = 2T(2) + 1 = 7
T(4) = 2T(3) + 1 = 15
T(5) = 2T(4) + 1 = 31 이다.
어라 패턴이 보인다
다음은 왠지 63일 것 같다.
그렇다
T(N) = 2^n-1 이다.
그래서 이를 출력문 맨 앞에 출력 해주면 된다.
내 해답
import sys
N = int(sys.stdin.readline())
def hanoi(N, start, end):
if N == 1:
print(start, end) # N이 1이라면 start에서 end로 옮겨버리면 끝.
return
sub = 6 - start - end # 1,2,3번 장대가 있기에 start+sub+end 는 6임을 이용하여 sub장대를 구할 수 있다.
hanoi(N - 1, start, sub) # N이 1이 아니라면 N-1을 start 에서 sub로 옮기겠다.
print(start, end) # start에 남은 맨 바닥 탑을 end로 보내고
hanoi(N - 1, sub, end) #그리고 sub에 있는 원판들을 end로 보내면 끝.
print(2**N - 1) # 옮기는 횟수는 2^N - 1 이다.
hanoi(N,1,3)