하노이탑(k번째 이동) > 문제은행



문제은행

1988 : 하노이탑(k번째 이동)

제한시간: 2000 ms    메모리제한: 64 MB
해결횟수: 13 회    시도횟수: 37 회   



하노이 탑 문제를 들어 보았을 것이다. 

3개의 막대기 중 하나에 n개의 원판이 꽂혀 있고, 이 원판들을 다른 막대기로 옮기는 문제이다. 

이 문제를 풀 때의 이동 회수가 2n-1임은 잘 알려져 있다.


하노이 탑에서 n개의 원판이 있을 경우에 이 원판의 이동 경로를 모두 출력하는 프로그램을 만드는 것은 쉬운 일이다.

하지만 n이 커지면 출력 개수가 2n-1이기 때문에 출력하지 못한다. (일반적인 하노이 문제와 같이 막대는 항상 3개로 한다.)


당신이 할 일은, 원판이 n개 있을 때, 최소한의 횟수로 이동시키는 방법 중에서, k번째에 어떤 작업을 수행해야 하는지를 출력하는 것이다. 

k번째만을 출력하면 된다. 물론 k는 1에서 2n-1까지의 정수이다. 제한시간은 2초이다.


 




첫째 줄에 디스크의 수를 정수 n(1 ≤ n ≤60)과 몇 번째 이동값k(1 ≤ k ≤ 2n-1)가 주어진다.
각 디스크들의 번호는 1, 2, ..., n이며, 잘못된 입력은 주어지지 않는다.



k번째 순서에서 몇 번째 원판을 몇 번째 막대기에서 몇 번째 막대기로 이동시키는지 출력한다.
예를 들면 3번 원판을 1번 막대에서 2번 막대로 움직일 경우엔 3 : 1 -> 2 로 출력한다.
숫자와 : -> 사이는 공백으로 구분하며 ->내부에는 공백이 없어야한다.


3 4
3 : 1 -> 3


4 10
2 : 2 -> 1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.