11729번 - 하노이 탑 이동 순서
이 문제의 정석은 당연히 재귀로 푸는 것입니다.
강의에 나올 정도로 굉장히 유명한 문제이며 재귀 연습하기 딱 좋은 문제입니다.
그러나 솔직히 말씀드리면 저는 풀이를 보고도 재귀로는 이해하기 너무 힘들었습니다.
정확히 말해 저는 탑 다운 방식(메모이제이션)에 약한 편입니다.
그래서 저는 "내가 알고 있기로는 재귀로 해결할 수 있고 트리가 강제되지 않는 경우 초기식과 점화식이 존재하니 dp로 해결할 수 있을까?"라는 질문에서 시작하여 다른 방법을 찾고 있었습니다.
그러다 결국 답을 찾았습니다. 이 문제는 dp로 해결 가능합니다---------
자, 우선 초기식을 생각해야 합니다.
초기식은 무엇일까요? N = 1인 경우입니다.
단순히 1->3만 하면 끝이지만 점화식이 요구된다면 1->3 뿐만 아니라 1->2, 2->3 등의 경우도 모두 신경 써야 합니다.
a를 출발 기둥, b를 도착 기둥이라고 할 때 초기식은 다음과 같습니다.
1->2 : (1, 2)
1->3 : (1, 3)
2->1 : (2, 1)
2->3 : (2, 3)
3->1 : (3, 1)
3->2 : (3, 2)
이것을 dp 리스트로 변환하면 다음과 같은 초기식을 도출할 수 있습니다.
dp[0][1][2] = [(1, 2)]
dp[0][1][3] = [(1, 3)]
dp[0][2][1] = [(2, 1)]
dp[0][2][3] = [(2, 3)]
dp[0][3][1] = [(3, 1)]
dp[0][3][2] = [(3, 2)]
---------------------------
초기식을 구했으니 이제 점화식을 유도하겠습니다.
우선 N = 2로 생각합니다.
1->3으로 갈려면 [(1, 2), (1, 3), (2, 3)] 순서로 진행되어야 합니다.
즉, dp[1][1][3] = [(1, 2), (1, 3), (2, 3)]이 됩니다.
그리고 나머지 경우들도 모두 구해줍니다.
dp[1][1][2] = [(1, 3), (1, 2), (3, 2)]
dp[1][1][3] = [(1, 2), (1, 3), (2, 3)]
dp[1][2][1] = [(2, 3), (2, 1), (3, 1)]
dp[1][2][3] = [(2, 1), (2, 3), (1, 3)]
dp[1][3][1] = [(3, 2), (3, 1), (2, 1)]
dp[1][3][2] = [(3, 1), (3, 2), (1, 2)]
이것만으로는 감이 안 잡히죠?
그러면 이번엔 N = 3일 때 1->3을 생각해볼까요?
N = 3인 경우 1->3이면 문제에 나온대로 dp[2][1][3] = [(1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)] 순서로 진행됩니다.
그런데 잘 관찰해 봅니다.
dp[1][1][3]에서 가운데를 보니 정확히 (a, b)로 되어 있습니다. 그리고 왼쪽에는 (a, c), 오른쪽 에는 (c, b)로 이루어져 있습니다.(a, b, c = 1, 3, 2)
그리고 그 다음에 dp[2][1][3]를 관찰하면 정확히 가운데에 (a, b) 딱 한 개가 보이고
왼쪽을 보면 [(1, 3), (1, 2), (3, 2)]인데 이것은 dp[1][1][2]와 일치합니다.
그리고 오른쪽을 보면 [(2, 1), (2, 3), (1, 3)]인데 이것은 dp[1][2][3]와 일치합니다.
패턴을 파악해보면 왼쪽은 dp[i-1][a][c], 오른쪽은 dp[i-1][c][b]로 추측할 수 있습니다.
왜 그럴까요?
우선 n개의 장대가 a 기둥에 있다면 b 기둥으로 옮기기 위해 먼저 n-1개의 장대들을 모두 c 기둥으로 옮겨야 합니다.(1번째 과정)
그 다음에 가장 큰 장대 1개를 a 기둥에서 b 기둥으로 옮깁니다.(2번째 과정)
마지막으로 c 기둥에 있는 모든 n-1개의 장대들을 b 기둥에 옮기면 끝입니다.(3번째 과정)
1번째 과정이 dp[i-1][a][c], 2번째 과정이 dp[0][a][b], 3번째 과정이 dp[i-1][c][b]입니다.
즉, 다음과 같은 점화식이 유도됩니다.
dp[i][a][b] = dp[i-1][a][c] + dp[0][a][b] + dp[i-1][c][b]
--------------------------------------------------------------------
정리하면 초기식과 점화식은 다음과 같습니다.
[초기식]
[점화식]
dp[i][a][b] = dp[i-1][a][c] + dp[0][a][b] + dp[i-1][c][b](i는 1 이상 n 미만, (a, b, c)는 1,2,3이 각각 1개씩만 존재)
이 때 (a, b, c)는 총 6가지가 존재하며 이 6가지들을 모두 적용해야 합니다.
이런 과정을 거쳐서 최종적으로 n개의 장대들을 a 기둥에서 b 기둥으로 옮기는 과정, dp[-1][a][b]를 출력 형식에 맞게 출력하면 됩니다.
추가로 이 방식은 1->3 뿐만 아니라 1->2, 3->1 등 다른 출발 기둥 및 도착 기둥을 설정해도 바로 답을 구할 수 있으므로 Q개의 쿼리문들을 실행해도 문제 없습니다.
(재귀 방식은 쿼리 하나 실행할 때마다 다시 처음부터 연산해야 한다는 문제점 발생하므로 여러 개의 쿼리를 실행해야 하는 경우 dp가 더 잘 맞습니다.)
댓글을 작성하려면 로그인해야 합니다.
kjk9704 11달 전 7
이 문제의 정석은 당연히 재귀로 푸는 것입니다.
강의에 나올 정도로 굉장히 유명한 문제이며 재귀 연습하기 딱 좋은 문제입니다.
그러나 솔직히 말씀드리면 저는 풀이를 보고도 재귀로는 이해하기 너무 힘들었습니다.
정확히 말해 저는 탑 다운 방식(메모이제이션)에 약한 편입니다.
그래서 저는 "내가 알고 있기로는 재귀로 해결할 수 있고 트리가 강제되지 않는 경우 초기식과 점화식이 존재하니 dp로 해결할 수 있을까?"라는 질문에서 시작하여 다른 방법을 찾고 있었습니다.
그러다 결국 답을 찾았습니다. 이 문제는 dp로 해결 가능합니다
---------
자, 우선 초기식을 생각해야 합니다.
초기식은 무엇일까요? N = 1인 경우입니다.
단순히 1->3만 하면 끝이지만 점화식이 요구된다면 1->3 뿐만 아니라 1->2, 2->3 등의 경우도 모두 신경 써야 합니다.
a를 출발 기둥, b를 도착 기둥이라고 할 때 초기식은 다음과 같습니다.
1->2 : (1, 2)
1->3 : (1, 3)
2->1 : (2, 1)
2->3 : (2, 3)
3->1 : (3, 1)
3->2 : (3, 2)
이것을 dp 리스트로 변환하면 다음과 같은 초기식을 도출할 수 있습니다.
dp[0][1][2] = [(1, 2)]
dp[0][1][3] = [(1, 3)]
dp[0][2][1] = [(2, 1)]
dp[0][2][3] = [(2, 3)]
dp[0][3][1] = [(3, 1)]
dp[0][3][2] = [(3, 2)]
---------------------------
초기식을 구했으니 이제 점화식을 유도하겠습니다.
우선 N = 2로 생각합니다.
1->3으로 갈려면 [(1, 2), (1, 3), (2, 3)] 순서로 진행되어야 합니다.
즉, dp[1][1][3] = [(1, 2), (1, 3), (2, 3)]이 됩니다.
그리고 나머지 경우들도 모두 구해줍니다.
dp[1][1][2] = [(1, 3), (1, 2), (3, 2)]
dp[1][1][3] = [(1, 2), (1, 3), (2, 3)]
dp[1][2][1] = [(2, 3), (2, 1), (3, 1)]
dp[1][2][3] = [(2, 1), (2, 3), (1, 3)]
dp[1][3][1] = [(3, 2), (3, 1), (2, 1)]
dp[1][3][2] = [(3, 1), (3, 2), (1, 2)]
이것만으로는 감이 안 잡히죠?
그러면 이번엔 N = 3일 때 1->3을 생각해볼까요?
N = 3인 경우 1->3이면 문제에 나온대로 dp[2][1][3] = [(1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)] 순서로 진행됩니다.
그런데 잘 관찰해 봅니다.
dp[1][1][3]에서 가운데를 보니 정확히 (a, b)로 되어 있습니다. 그리고 왼쪽에는 (a, c), 오른쪽 에는 (c, b)로 이루어져 있습니다.(a, b, c = 1, 3, 2)
그리고 그 다음에 dp[2][1][3]를 관찰하면 정확히 가운데에 (a, b) 딱 한 개가 보이고
왼쪽을 보면 [(1, 3), (1, 2), (3, 2)]인데 이것은 dp[1][1][2]와 일치합니다.
그리고 오른쪽을 보면 [(2, 1), (2, 3), (1, 3)]인데 이것은 dp[1][2][3]와 일치합니다.
패턴을 파악해보면 왼쪽은 dp[i-1][a][c], 오른쪽은 dp[i-1][c][b]로 추측할 수 있습니다.
왜 그럴까요?
우선 n개의 장대가 a 기둥에 있다면 b 기둥으로 옮기기 위해 먼저 n-1개의 장대들을 모두 c 기둥으로 옮겨야 합니다.(1번째 과정)
그 다음에 가장 큰 장대 1개를 a 기둥에서 b 기둥으로 옮깁니다.(2번째 과정)
마지막으로 c 기둥에 있는 모든 n-1개의 장대들을 b 기둥에 옮기면 끝입니다.(3번째 과정)
1번째 과정이 dp[i-1][a][c], 2번째 과정이 dp[0][a][b], 3번째 과정이 dp[i-1][c][b]입니다.
즉, 다음과 같은 점화식이 유도됩니다.
dp[i][a][b] = dp[i-1][a][c] + dp[0][a][b] + dp[i-1][c][b]
--------------------------------------------------------------------
정리하면 초기식과 점화식은 다음과 같습니다.
[초기식]
dp[0][1][2] = [(1, 2)]
dp[0][1][3] = [(1, 3)]
dp[0][2][1] = [(2, 1)]
dp[0][2][3] = [(2, 3)]
dp[0][3][1] = [(3, 1)]
dp[0][3][2] = [(3, 2)]
[점화식]
dp[i][a][b] = dp[i-1][a][c] + dp[0][a][b] + dp[i-1][c][b](i는 1 이상 n 미만, (a, b, c)는 1,2,3이 각각 1개씩만 존재)
이 때 (a, b, c)는 총 6가지가 존재하며 이 6가지들을 모두 적용해야 합니다.
이런 과정을 거쳐서 최종적으로 n개의 장대들을 a 기둥에서 b 기둥으로 옮기는 과정, dp[-1][a][b]를 출력 형식에 맞게 출력하면 됩니다.
추가로 이 방식은 1->3 뿐만 아니라 1->2, 3->1 등 다른 출발 기둥 및 도착 기둥을 설정해도 바로 답을 구할 수 있으므로 Q개의 쿼리문들을 실행해도 문제 없습니다.
(재귀 방식은 쿼리 하나 실행할 때마다 다시 처음부터 연산해야 한다는 문제점 발생하므로 여러 개의 쿼리를 실행해야 하는 경우 dp가 더 잘 맞습니다.)