1465: 요세푸스 문제에서 생존하기

요세푸스 문제는 유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제이다.

당시 예루살렘에서 살았던 요세푸스는 유대-로마 전쟁 때 유대군 장교로 참전했다가 동료 병사들, 자신을 포함해 총 41명과 함께 로마군에게 포위되었다.  동료들은 로마군의 손에 죽느니 스스로 죽겠다고 결심했다. 그러나 직접 자살하는 것이 어려웠는지, 그들은 서로를 제거하기 위한 알고리즘을 세운다. 

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

그러나 요세푸스는 동료들의 뜻에 반대하고 살고 싶었고, 수학적 논리력을 발휘하여 끝까지 살기 위한 자리를 찾고자 한다.

N과 K가 주어지면, 마지막으로 남는 사람의 번호를 구하는 프로그램을 작성하시오.

7 3

4