[프로그래머스] 하노이의 탑 - PYTHON

문제보기

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

풀이 & 코드

전의 문제랑 난이도가 너무 달라서 오히려 당황했다. 문제를 선정할 때 정답률을 기준으로 난이도를 측정했는 데 나온지 얼마 안된 문제라 정답률이 제대로 측정이 되지 않았나 보다. (문제 푸는 것 보다 포스팅 하는게 더 오래 걸릴 것으로 예상된다..) 

 

혹시 나처럼 return 값을 이해 못해 당황하는 사람들이 있을 까봐 먼저 작성해 놓는다. return값은 원판을 옮기는 순서를 의미한다. n이 2일때의 return 값인 [[1,2],[1,3],[2,3]]은 아래 사진처럼 1에 있는 원판을 2로 옮기고, 1에 있는 원판을 3으로 옮기고, 2에 있는 원판을 3으로 옮기는 것을 의미한다!

 

하노이 탑

 

맨 처음 아이디어를 얻기 위해 n=3, n=4 일때 원판 옮기는 방식을 수기로 작성해 봤다. 탑3에 모든 원판들을 쌓기 위해서는 가장 큰 원판이 비워있는 탑3으로 가야한다. 그러기 위해서는 탑1에 있는 원판들 중 가장 큰 것을 제외하고 탑2로 옮겨져야 한다는 의미이다. 그 후에 탑2에 있는 원판들을 그대로 탑3으로 옮기면 된다. 맞다! DP문제다. 여기까지 아이디어가 흐르자 바로 move_tower함수를 작성했다.

 

s = 원판들의 시작 탑, m = 중간에 있는 탑, e = 도착해야하는 탑, n = 옮겨야하는 원판의 개수 로 파라미터를 작성했고 나머지는 풀이랑 코드를 읽으면 잘 이해 될 것으로 예상된다!

 

 

def move_tower(s, m, e, n):
    return [[s, e]] if n == 1 else move_tower(s, e, m, n-1) + [[s, e]] +  move_tower(m, s, e, n-1)
    
def solution(n):
    return move_tower(1,2,3,n)