[백준][python][11729] 하노이 탑 이동 순서

문제 내용은 위와 같다.

 

이 문제를 풀기 위해서 접근 방식을 먼저 생각하기 보다는 일단 방법을 간단하게 나열해 보았다.

만약 원판의 개수가 1이라면 

1 3

과 같은 형식이 된다

원판의 개수가 2라면 

1 2 

1 3

2 3

이 된다. 

원판의 개수가 3이라면 위 그림과 같은 상황이 벌어진다. 

 

눈치가 빠른 사람은 벌써 규칙을 찾아 냈을 것이라고 생각한다.

아직 이해가 가지 않은 사람들을 위해서 설명을 해보자면 이 문제의 포인트는 맨 아래에 있는 원판을 3번째 탑으로 옮기는 것이다. 

또한 이것을 기준으로 위쪽의 개수와 아랫쪽의 개수가 같다. 

 

이것이 의미하는 것이 무엇일까?

바로 설명을 해보자면,

1. 맨 아래 원판(가장 큰 원판)을 제외한 나머지 원판을 모두 2번째 탑으로 옮긴다.

2. 맨 아래 원판을 3번째 탑으로 옮긴다.

3. 2번째 탑을 3번째 탑으로 옮긴다.

이렇게 된다.

 

이것을 프로그램으로 구현하기 위해서는 재귀함수를 쓰는 것이 편할 것이다. 왜냐하면 1번째와 3번째가 반복해서 일어나고 이 과정 자체가 N-1번째의 과정을 반복하는 것이기 때문이다. 

 

def 재귀(N, start, goal):

    if N == 1:

        print("{} {}".format(start, goal))

        return

    재귀(N-1, start, 6-start-goal), 재귀(1, start, goal), 재귀(N-1, 6-start-goal, goal)

 

N = int(input())

 

print(2**N - 1)

 

재귀(N, 1, 3)

 

나는 이런 식으로 코드를 구성해 보았다. 시작과 끝을 지정하게 만들어서 그것을 기준으로 반복하게 만들었다.

하지만 나는 아직 초보자이기 때문에 여러분은 나보다 훨씬 멋지고 깔끔한 코드를 만들 것이다!

부디 지저분한 코드라고 욕하지 말아주길 바란다 ^^.