문제

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

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

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

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

입력

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

출력

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

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력 1

예제 출력 1

Solution

[문제 이해]

마지막 원판을 목표자리로 옮기기 위해서는 마지막 원판부터 1번째 원판까지 경로를 재귀로 풀어야겠다고 생각
→ 처리하는 원판 순서 : n → n -1 → n -2 … → 1
K를 구하는 규칙은 2^n - 1 식을 이용하면 될 것 같음
→ 총 이동 횟수
이동하는 장소가 3개로 제한적이라 장소를 가지고 연산

이해한 내용을 바탕으로 코드를 작성했습니다.

[코드]

import sys
input = sys.stdin.readline

def hanoi(n, x, y, z):
    # 총 원판이 1개인 경우는 이동 경로가 1가지라 바로 반환
    if n == 1:
        print(x, z)
    else:
        # n원판이 3번 자리로 가야 하기 때문에 n-1번 원판은 2번 자리로 이동
        hanoi(n-1, x, z, y)
        print(x, z)
        # n-1번 원판이 n번 원판 위에 올라가야 하기 때문에 3번 자리로 이동
        hanoi(n-1, y, x, z)

if __name__ == '__main__':
    N = int(input())
    # 2의 n승 -1 -> 원판 총 이동 횟수
    K = (2**N) - 1
    print(K)
    hanoi(N, 1, 2, 3)

[여담]

재귀는 복잡하거나 반복적인 것을 참 단순하게 표현할 수 있어서 좋습니다.

하지만 복잡한 것을 단순하게 보여줘서 내용을 머리에서 떠올려보기가 좀 어렵습니다.

아래는 데코레이터 의 엄청난 성능을 볼 수 있었던 코드입니다.

[데코레이터 코드]

import sys
input = sys.stdin.readline

# dictionary 구조에 출력할 데이터를 저장하는 데코레이터
def cacheable(func):
    cache = {}

    def u(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return u

@cacheable
def hanoi_cache(n, s=1, e=3):
    # n이 0인 경우는 이동이 없으므로 ''
    if n == 0:
        return ''
    # 마지막에 1번의 출력을 위한 경로를 담기위한 리스트
    res = []
    # 2번과 3번 자리를 표현한 것 같음
    t = 6 - s - e
    # 위 코드의 hanoi(n-1, x, z, y)와 동일한 역할
    res.append(hanoi_cache(n - 1, s, t))
    # 경로 이동 과정
    res.append(f'{s} {e}\n')
    # 위 코드의 hanoi(n-1, y, x, z)와 동일한 역할
    res.append(hanoi_cache(n - 1, t, e))

    # 리스트에 담아뒀던 경로를 하나의 문자열로 합치기
    return ''.join(res)

if __name__ == '__main__':
    n = int(input())
    print(2 ** n - 1)
    print(hanoi_cache(n))

print() 함수가 생각보다 많은 리소스를 사용하는 것을 알고 있었습니다.

그렇기에 이 코드는 정말 제대로라는 생각이 들었습니다.

janos 코드 실행시간 → 936ms
데코레이터 를 활용한 코드 실행시간 → 92ms

출력을 최소화하여 10배 가량의 성능 차이를 보였습니다.

대박