[구현/재귀] boj.1914 하노이

문제 해석

처음에는 하노이 이동 횟수를 구하기 위해 DP를 사용하였다. 점화식을 세워보니 이전 결과를 계속 사용한다 느껴서 DP가 적절할 것이라고 생각한 게 문제였다.

실제 정답을 얻을 수 있었던 코드는 하노이의 탑을 이해한 채로, 단순 구현으로 접근하면 풀 수 있었다..!

교훈 :

문제 풀이를 위한 알고리즘을 선택할 땐 신중하게 따져보자... DP는 누적되는 값을 사용한다 하더라도, 일회성으로 값을 구할땐 비효율적이다!

풀이 코드

첫 번째 시도 : 메모리 초과

import sys
input = sys.stdin.readline

def hanoi_res(n):
    if n <= 1:
        return res[n]
    elif res[n] != 0:
        return res[n]
    res[n] = hanoi_res(n - 1) * 2 + 1
    return res[n]

def convert(li, a, b):
    ret = list()
    for i, j in li:
        if i == a: i = b
        elif i == b: i = a
        if j == a: j = b
        elif j == b: j = a
        ret.append((i, j))
    return ret

def hanoi_mov(n):
    if n == 1:
        return mov[0]
    return mov[n-1]

n = int(input())
res = [0] * (n + 1)
res[1] = 1
mov = [[(1,3)]]
for i in range(1, n):
    mov.append([*convert(mov[i-1], 2, 3), (1, 3), *convert(mov[i-1], 1, 2)])

print(hanoi_res(n))
for i in hanoi_mov(n):
    print(*i)

두 번째 시도 : 메모리 초과
위 방식에서 메모리 초과가 난 이유는, 하노이 탑의 원판을 옮기는 작업 과정을 저장하는 mov배열에 너무 많은 데이터를 계속 담아두려고 하기 때문이라고 가정하였다.

따라서 해당 값을 다 저장하지 않고, 필요한 값을 얻을 수 있을 때까지 임시 값으로만 저장해가며 올라가기로 했다.

import sys
input = sys.stdin.readline

def hanoi_res(n):
    if n <= 1:
        return res[n]
    elif res[n] != 0:
        return res[n]
    res[n] = hanoi_res(n - 1) * 2 + 1
    return res[n]

def convert(li, a, b):
    ret = list()
    for i, j in li:
        if i == a: i = b
        elif i == b: i = a
        if j == a: j = b
        elif j == b: j = a
        ret.append((i, j))
    return ret
def hanoi_mov(n, tmp):
    if n == 1:
        return tmp
    for i in range(1,n):
        tmp = [*convert(tmp, 2, 3), (1, 3), *convert(tmp, 1, 2)]
    return tmp

n = int(input())
res = [0] * (n + 1)
res[1] = 1

print(hanoi_res(n))
for i in hanoi_mov(n, [(1,3)]):
    print(*i)

세 번째 시도 : 정답
위에서도 메모리 초과가 난다고 하여 다시 봐보니, 우선 ret배열이 굳이 쓰일 필요가 없을 것 같아서 convert 함수를 지우기로 했다. ret 배열을 사용함으로써 메모리를 많이 쓰는 배열이 굳이 여러개 사용된다는 느낌을 받아서였다.
라고 생각했는데,... 아니였다.

DP로 풀어볼기라고 기를 쓴 게 화근이었다. 많은 양의 연산을 수행해야 하므로 DP로 저장해가며 올라가는 것보다 그냥 답만 얻을 수 있도록 연산하는 방식이 더 효율적인 방식이었다. 물론 이게 프로그램 개발이라면 DP와 같은 방식이 적용되면 계속 사용될 때 용이하겠지만, 이 경우에선 나처럼 DP를 사용하여 한 번의 답을 얻기 위해 이전 과정을 전부 안고 가려고 하는 사람들을 겨냥하여 비효율적이라는 교훈을 주기 위해 공간복잡도를 세게 걸어두신 것 같다.

import sys
input = sys.stdin.readline
def hanoi_res(n):
    if n == 1:
        return 1
    res = 1
    for i in range(1,n):
        res = res * 2 + 1
    return res

def convert(li, a, b):
    ret = list()
    for i, j in li:
        if i == a: i = b
        elif i == b: i = a
        if j == a: j = b
        elif j == b: j = a
        ret.append((i, j))
    return ret
def hanoi_mov(n, tmp):
    if n == 1:
        return tmp
    for i in range(1,n):
        tmp = [*convert(tmp, 2, 3), (1, 3), *convert(tmp, 1, 2)]
    return tmp

n = int(input())

print(hanoi_res(n))
if n <= 20:
    for i in hanoi_mov(n, [(1,3)]):
        print(*i)

일반적인 풀이

보통은 재귀로 푼다고 한다...ㅎㅎㅎ 머리를 더 효율적으로 굴려보는 훈련을 하자.

import sys
input = sys.stdin.readline

def hanoi(N, start, end, mid):
	if N == 1:
		print(start, end)
		return
	
	hanoi(N-1, start, mid, end)
	print(start, end)
	hanoi(N-1, mid, end, start)

N = int(input())

print(2**N - 1)

if N <= 20:
	hanoi(N, 1, 3, 2)