요셉문제 (연결리스트 사용하기) |
---|
카메롯 성에서는 회의가 열리고 있다. 밤마다 용이 나타나서 백성들을 괴롭히기 때문이다. 원탁의 기사 모두가 용과 싸우고 싶어하지만 많은 군대를 이끌고 가면 용이 미리 알아채기 때문에 기사 한 명만이 갈 수 있다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다. 그러던 중 란슬러트가 묘안을 제시하였다. 원탁에 둘러앉아 있는 기사 n명에게 시계방향으로 차례대로 1번부터 n번의 번호를 부여한다. 다음 그 중 임의의 숫자 m을 선택하여 그 번호의 기사를 제외시킨다. 다음 그 기사로부터 시계 방향으로 k번째 있는 기사를 선택하여 제외시킨다. 이렇게 제외된 기사로부터 k번째 있는 기사를 제외시키는 작업을 단 한 명이 남을 때까지 계속한 뒤, 그 결과 마지막으로 나은 기사가 용과 싸우러 가는 것이다. 예를 들어, n=8, m=2, k=3인 경우, 2번 기사가 먼저 제외된 후, 이어 5번, 8번 기사가 차례대로 제외된다. 원탁의 기사의 n, 처음 선택한 기사의 번호 m, 다음으로 몇 번째 기사를 제외시킬 것인가 하는 k가 주어질 때, 제외되는 기사들의 번호를 순서대로 출력하고, 용과 싸우러 가게 되는 기사의 번호를 출력하는 프로그램을 작성하시오. |
입력 | |
---|---|
첫 줄에 n, m, k가 차례대로 공백을 사이에 두고 주어진다. 단, n<=1000 이고, m, k<=n 이다. |
출력 | |
---|---|
첫째 줄에 제외되는 기사들의 번호를 제외되는 순서대로 출력한다. 둘째 줄에 마지막까지 남아 용과 싸우러 가게 되는 기사의 번호를 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 8 2 3 | |
출력 | 2 5 8 4 1 7 3 6 |