[백준 | Python] #31248 - 3+1 하노이 탑

31248번: 3+1 하노이 탑

 

아이디어

D 기둥에 있는 원판은 다시 옮길 수 없다는 게 핵심적인 제한 요소인 것 같아 보인다.

그 말은 D 기둥은 무조건 가장 큰 원판부터 쌓아야 함을 의미한다.

이를 위해 $N$개의 원판에 대해 다음과 같은 과정을 떠올렸다.

 

제일 큰 원판 두 개를 제외한 나머지 원판 $N-2$개를 D를 제외한 빈 기둥 중 아무 곳으로 옮긴다.

두 번째로 큰 원판을 D를 제외한 빈 기둥으로 옮긴다.

제일 큰 원판을 D로 옮긴다.

두 번째로 큰 원판을 D로 옮긴다.

나머지 $N-2$개의 원판에 대해 위의 과정을 반복한다.

 

구현

입력 $N$이 들어오면 $N-2$개에 대해 일반적인 하노이탑 문제를 푼다.

큰 원판 2개를 D로 옮긴다.

$N$을 2씩 줄여가며 위 과정을 $N\geq2$를 만족하는 동안 반복한다.

반복 후에 $N==1$이면 예외 처리를 한다.

 

위 과정에서 이동 수를 하나씩 세 줘도 되지만 나는 규칙성을 파악해서 다이나믹 프로그래밍으로 계산하였다.

그 과정은 아래 dp 배열에 포함되어 있다.

 

코드

def move(tiles, s, e):
    if tiles == 0:
        return

    move(tiles-1, s, 3-s-e)
    print('ABC'[s], 'ABC'[e])
    move(tiles-1, 3-s-e, e)

n = int(input())

dp = [0,1]
for i in range(2,21):
    dp.append(2**(i-2)-1 + 3 + dp[i-2])
print(dp[n])

disk_pos = 0
while n >= 2:
    move(n-2, disk_pos, 2-disk_pos)
    print('ABC'[disk_pos], 'B')
    print('ABC'[disk_pos], 'D')
    print('B', 'D')

    n -= 2
    disk_pos = 2-disk_pos

if n == 1:
    print('ABC'[disk_pos], 'D')

 

 

숏코딩

숏코딩도 해보았다. 167 Bytes

함수의 인자의 기본값 설정을 통해 2 Bytes를 줄인 트릭은 개인적으로도 감탄스럽다.

x='_ABCD'
def m(t,s,e=4):
 if t:m(t-1,s,k:=[s^e,2][e>3]);print(x[s],x[e]);m(t-1,k,e)
n=int(input())
print(n+~-2**n//3)
p=1
while n>1:m(n:=n-2,p,p^2);m(2,p);p^=2
m(n,p)