경기도 정보올림피아드 알고리즘- 하노이탑(k번째 이동) > 문제은행 : 정보올림피아드&알고리즘



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

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
10 회   
시도횟수
27 회   

문제

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

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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP