오영식의 보물
시간 제한1초메모리 제한128 MB
모든 원반이 A에 있는 초기 상태에서 주어진 목표 상태까지 가는 최단 이동 순서를 구해서 정확히 M번 이동한 뒤의 원반 배치를 출력합니다.
문제
오영식의 보물은 하노이에 있는 하노이 탑의 모형이다. 하노이 탑은 왼쪽부터 A, B, C라고 부르는 세 막대와, 크기가 1부터 N까지인 N개의 원반으로 이루어져 있다. 처음에는 모든 원반이 막대 A에 놓여 있다. 같은 막대에서는 큰 원반이 작은 원반보다 아래에 있어야 하므로, 처음에는 크기 N인 원반이 가장 아래에 있고 크기 1인 원반이 가장 위에 있다. 원반은 한 번에 하나씩만 옮길 수 있다.
민식이는 영식이와 함께 하노이 탑을 옮기며 놀고 싶었다. 두 사람은 모든 원반을 A에서 C로 옮기는 일반적인 놀이를 이미 많이 했기 때문에, 다솜이는 새로운 규칙을 제안했다. 먼저 다솜이가 규칙에 따라 도달할 수 있는 적절한 상태를 보여준다. 처음 상태에서 그 상태로 가는 최소 이동 경로를 생각할 때, 정확히 M번 이동한 뒤의 하노이 탑 상태를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 원반의 개수 N과 수행해야 하는 이동 횟수 M이 주어진다. 둘째 줄에는 다솜이가 보여준 목표 상태가 문자열로 주어진다. 모든 문자는 A, B, C 중 하나이다. 문자열의 첫 번째 문자는 1번 원반이 있는 막대를, 두 번째 문자는 2번 원반이 있는 막대를 나타내며, 일반적으로 i번째 문자는 i+1번 원반이 있는 막대를 나타낸다.
N은 30 이하의 자연수이다. M은 0 <= M <= m을 만족하는 정수이며, m은 처음 상태에서 입력으로 주어진 상태에 도달하는 데 필요한 최소 이동 횟수이다.
출력
입력의 상태 문자열과 같은 형식으로 하노이 탑의 상태를 한 줄에 출력한다.
힌트
N=3이고 목표 상태가 CCC라면, AAA에서 CCC로 가는 최소 이동 경로는 AAA -> CAA -> CBA -> BBA -> BBC -> ABC -> ACC -> CCC 이다.