문제풀이

[PY] 1914 : 하노이 탑

pwerty 2025. 3. 20. 11:26

https://www.acmicpc.net/problem/1914

얘는 진짜 풀었던거라 금방 하고 넘어갔어야 했는데 막상 중요한 내용이 기억이 안났다.
좀 민망할 정도로 극단적으로 요약하면 이런 견적이 나온다.

  • n-1번째까지를 2번 기둥에 치운다.
  • n번째를 1번 기둥에서 3번 기둥으로 옮긴다.
  • n-1번째까지를 2번 기둥에서 3번으로 마저 옮겨준다.

어찌 되었건 n 이전에 n-1이 옮겨져야 하는 것은 당연하다.
따라서, 그럼 단계에 대한 매개변수를 하나 쓸건데, 이걸 n이라고 해야겠다.

그리고 str, dest 즉 출발지와 도착지를 지정해주어야 하는데, 이 부분이 떠오를랑 말랑 해서 결과적으로 그냥 처음부터 끝까지 그렸다.

5개의 플레이트가 주어지는 경우를 그린 상황이다. 할 말이 참 많지만 전체적인 전개는 이런식으로 진행이 된다.

base condition은 n이 1일 때 이다. 이 때는 대상 플레이트는 한 개이니 특별히 상관없이 수행 할 수 있다.

그렇지 않은 경우 아래와 같이 진행 할 수 있다 :

n-1번째 플레이트를 str에서 6-str-dest로 옮기는 시도를 한다.
n번째 플레이트를 str에서 dest로 옮긴다.
n-1번째 플레이트를 6-str-dest를 dest로 옮긴다.

1 2가 주어지면 3이 나오고, 3 2가 주어지면 1이 나오고, 3 1이 주어지면 2가 나오는 영역까지 왔는데 6-str-dest라는 식은 생각해내는데 몇 번이나 시도 했어야만 했다.

        goHanoi(diskNum - 1, sr, 6 - sr - en)
        if caseCnt <= 20:  # 최대 20번만 출력
            print('{} {}'. format(sr, en))
        totalValue += 1
        goHanoi(diskNum - 1, 6 - sr - en, en)

핵심은 이렇게 끝난다.

추가적으로 caseCnt <= 20 조건 때문에 상당히 당황스러웠다. 실제로 저기에 들어가는 코드는 아니고, 출력 영역에서 다루는 코드라 큰 의미는 없지만.. 어쨌든, 원하는게 뭔지 도식화를 잘 해야겠다는 생각을 들게하는 문제였다.

import sys
totalValue = 0
result = []

def getMultiple(num):
    return 2 ** num

def goHanoi(diskNum, sr, en):
    global totalValue
    if diskNum == 1: 
        if caseCnt <= 20:  # 최대 20번만 출력
            print('{} {}'. format(sr, en))
        totalValue += 1
        return
    else:
        goHanoi(diskNum - 1, sr, 6 - sr - en)
        if caseCnt <= 20:  # 최대 20번만 출력
            print('{} {}'. format(sr, en))
        totalValue += 1
        goHanoi(diskNum - 1, 6 - sr - en, en)


caseCnt = int(sys.stdin.readline())
hanoiCnt = int(getMultiple(caseCnt)) - 1
print(hanoiCnt)

if(caseCnt <= 20):
    goHanoi(caseCnt, 1, 3)

 

댓글수0