알고리즘 :: 원탁의 기사 (The Knights of the Round Table)
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…
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkedListType.h"
int main (int argc, char **argv)
{
LinkedListType knights;
int number, start, course;
int k;
if ((argc != 2) || (strlen (argv[1]) != 3))
{
printf ("[+] $./KnightsOfRound [number][start][course]\n");
printf ("[+] each value is between 0 and 9.\n");
return 1;
}
number = atoi (argv[1]) / 100;
start = atoi (argv[1]) % 100 / 10;
course = atoi (argv[1]) % 10;
init (&knights);
for (k = 0; k < number; k++)
insert_node (&knights, k + 1);
for (k = 0; k < start; k++)
get_next_node (&knights);
while (!is_empty (&knights))
{
printf ("%d", get_node (&knights)->data);
remove_node (&knights);
for (k = 0; k < course; k++)
get_next_node (&knights);
}
printf ("\n");
return 0;
}Output
참고문헌
자료구조 :: 양방향 원형 연결리스트 :: /?p=920- 자료구조 :: 양방향 원형 연결리스트