7개의 댓글이 있습니다.
-
-
Kyungryeol -
a[n][k] = "n개의 disc와 k개의 pole을 이용해서 문제를 풀 때의 최소 이동 수"
로 가정하고 동적계획법을 사용하여 풀 수 있습니다.
http://acm.zju.edu.cn/show_problem.php?pid=2338
16년 전 link
-
-
-
Kyungryeol -
a[n][k] = "n개의 disc와 k개의 pole을 이용해서 문제를 풀 때의 최소 이동 수" 로 가정하겠습니다.
먼저 일반적인 하노이 탑 문제를 살펴보겠습니다.
문제는 어느 한 pole (pole A) 에서 다른 pole (pole B) 로 n개의 disc를 옮겨야 하는 것입니다.
그 과정으로 다른 하나의 pole (pole C) 에 n-1개의 disc를 임시로 옮겨놓고
가장 큰 disc를 pole A 에서 pole B로 옮긴 다음
다시 n-1개의 disc를 pole C 에서 pole B로 옮기는 것입니다.
즉, 옮기는 횟수의 점화식은 a[n][3] = a[n-1][3] + 1 + a[n-1][3] = 2*a[n-1][3]+1 이 됩니다.
여기서 1은 엄밀히 말하면 a[1][2] 가 되겠습니다.
a[1][3] = 1 이기 때문에 점화식을 풀면 a[n][3] = 2^n-1 이 되는 것이죠.
자 그럼 과연 k가 3 이상일 때는 점화식이 어떻게 될까요?
a[n][k] = min (a[j][k] + a[n-j][k-1] + a[j][k]), (1 <= j < n)
이런 형식이 되겠습니다.
먼저 j개의 disc를 어느 빈 pole에 옮기고 (a[j][k])
나머지 n-j개의 disc를 목표 pole에 옮깁니다 (a[n-j][k-1])
이 때, j개의 disc가 있는 pole을 이용할 수 없기 때문에 이용할 수 있는 pole의 수는 k-1 입니다.
그리고 다시 j개의 disc를 목표 pole에 옮기는 것이죠 (a[j][k])
이상 n개의 disc와 k개의 pole을 이용한 하노이 탑 점화식 설명이었습니다.
16년 전 link
-
-
-
Being -
제가 알기로, 구경렬님이 제시하신 점화식은 '가설'입니다. 즉, 최적해인지 증명은 되지 않았습니다. 그러나 알려진 최적해이므로 아마도 최적해가 아닐까 하고 생각되고 있습니다.
기본적인 아이디어는 과연 몇 개의 디스크를 덜어서 옮길 것인가 하는 것입니다. 기둥 3개짜리 하노이 탑에서는 항상 N-1개의 디스크를 덜어서 다른 곳에 임시로 옮겨 두고, 가장 큰 디스크를 타겟 기둥에 옮겼어야 하죠. 기둥이 여러 개인 경우, 임시로 작은 j개의 디스크를 옮겨 둔 뒤 큰 N-j개의 디스크를 타겟 기둥에 옮기고 옮겨둔 디스크들을 가져오는 거죠.
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Chevalier
하노이탑 문제를 공부하고 있는데요,
기둥 4개..를 넘어 5개를 풀어야 하는데..
쉽지 않네요.
어떤 식으로 풀어야 할까요?
점화식을 아시는 분 있으신가요?
16년 전