요세푸스 문제(Josephus problem)2 > 문제은행



문제은행

3102 : 요세푸스 문제(Josephus problem)2

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 12 회    시도횟수: 50 회   



전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

 

nk가 자연수이고, k < n이라고 가정한다

n명이 동그랗게 모여 있을 때 임의의 한 명부터 순서를 세어 나가서 k번째 사람을 모임에서 제외한다

남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다

이것을 아무도 남지 않을 때까지 계속해서 반복한다

이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 

마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다. - 참조 wikipedia -

 

nk를 입력 받아 요세푸스 순열 중에 마지막 세 사람을 구하는 프로그램을 작성해보자.

 

예를 들어 n = 5, k = 3이라고 할 경우

제외되는 사람들을 차례로 적어보면 3, 1, 5, 2, 4이다.

따라서 마지막 세 사람은 차례로 5, 2, 4가 된다.

 ​ 




두 정수 n과 k가 입력된다. (1 <= k < n, 3<= n <= 1,000,000)



하나의 행에 공백으로 구분하여 요세푸스 순열을 출력한다.


5 3
5 2 4


10 7
5 8 9


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.