[알고리즘] 원탁의 기사 (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
823Output Format
25841736『Programming Challenges: 알고리즘 트레이닝 북』 에 소개된 꽤 유명한 알고리즘 문제지요. 작년 HDCON 예선전에도 나왔던 문제이기도 하구요. 이 문제는 링크드리스트를 이용하면 쉽게 풀 수 있습니다. 아래는 지난 번 작성했던 1링크드리스트 라이브러리를 이용하여 작성한 소스입니다.
Solution
View source...
Output

참고문헌
자료구조 :: 양방향 원형 연결리스트 :: http://hisjournal.net/blog/301Footnote.
- 자료구조 :: 양방향 원형 연결리스트 [Back]
"#1. 내 머리 속의 노트 / 알고리즘, 각개격파!" 분류의 다른 글
| 자료구조 :: 양방향 원형 연결리스트 (0) | 2010/01/01 |
| 자료구조 :: 크기가 조정되는 배열 스택 (0) | 2009/12/20 |
| 알고리즘 :: 함수의 반환값을 범위 점검할 때 abs 함수를 응용하자. (2) | 2009/02/26 |
| 알고리즘 :: 최적화된 에라토스테네스의 체 (4) | 2009/02/23 |
| 알고리즘 :: floor 함수로 반올림하기 (5) | 2009/02/20 |
| 알고리즘 :: XOR 스왑 알고리즘의 문제점이 무엇일까? (0) | 2009/01/19 |
| 알고리즘 :: 소수인지 판별하는 알고리즘을 최적화하자. (4) | 2009/01/18 |
| 알고리즘 :: XOR 연산을 이용하여 스왑 알고리즘을 최적화하자. (0) | 2009/01/15 |
| 컴파일러도 "귀찮다" 라고 말하는 하노이 탑 문제 (2) | 2009/01/13 |
| 알고리즘 :: 입력된 수가 소수인지 확인하자. (2) | 2009/01/13 |
Trackback Address:http://hisjournal.net/blog/trackback/322