[알고리즘] 원탁의 기사 (The Knights of the Round Table)

2010/06/09 00:26

Question

원탁의 기사 모두가 용과 싸우고 싶어한다. 하지만 많은 군대를 이끌고 가면 용이 미리 알아채기 때문에 기사 한 명만이 갈 수 있다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다.

그러던 중 랜슬럿이 묘책을 제시하였다. 원탁에 둘러 앉아 있는 기사 n명에게 시계방향으로 차례대로 1번부터 n번의 번호를 부여 한다. 다음 그 중의 임의의 숫자 m을 선택하여 그 번호의 기사를 제외시킨다. 다음 그 기사로부터 시계방향으로 k번째 있는 기사를 제외시키는 작업을 단 한명이 남을때까지 계속한 뒤, 그 결과 마지막으로 남는 기사가 용과 싸우러 가는 것이다. 예를 들어 n=8, m=2, k=3인 경우, 2번째 기사가 먼저 제외된 후 이어 5번, 8번 기사가 차례대로 제외된다.

원탁의 기사의 수 n, 처음 선택한 기사의 번호 m, 다음으로 몇 번째 기사를 제외시킬 것인가 하는 k가 주어질때, 제외되는 기사들의 번호를 순서대로 출력하고, 용과 싸우러 가게 되는 기사의 번호를 출력하는 프로그램을 작성하시오.

Input Format

823

Output Format

25841736

Programming Challenges: 알고리즘 트레이닝 북』 에 소개된 꽤 유명한 알고리즘 문제지요. 작년 HDCON 예선전에도 나왔던 문제이기도 하구요. 이 문제는 링크드리스트를 이용하면 쉽게 풀 수 있습니다. 아래는 지난 번 작성했던 1링크드리스트 라이브러리를 이용하여 작성한 소스입니다.

Solution

View source...


Output


사용자 삽입 이미지

참고문헌

자료구조 :: 양방향 원형 연결리스트 :: http://hisjournal.net/blog/301
크리에이티브 커먼즈 라이센스
Creative Commons License
Footnote.
  1. 자료구조 :: 양방향 원형 연결리스트 [Back]

6l4ck3y3 #1. 내 머리 속의 노트/알고리즘, 각개격파! , ,

Trackback Address:http://hisjournal.net/blog/trackback/322
[로그인][오픈아이디란?]