Boj 11025) 요세푸스 문제 3

문제

백준 11025

설명

\[f(n, k) = (f(n-1, k) + k - 1 \mod n) + 1\]

요세푸스 수열의 마지막 항에 대한 점화식은 위와 같다.

이는 일대일 대응되는 수열 간의 변환 식을 유추하므로써 구할 수 있다. 다음을 살펴보자.

(n, k) 일때

4 5 6 7 1 2  // (7, 3) 에서 1회 수행 시 큐에 남는 수
1 2 3 4 5 6  // (6, 3) 에서 0회 수행 시 큐에 남는 수

4 5 6 1 2    // (6, 3) 에서 1회 수행시 큐에 남는 수
1 2 3 4 5    // (5, 3) 에서 0회 수행시 큐에 남는 수

...

1            // (2, 3) 에서 1 회 수행시 큐에 남는 수
1            // (1, 3) 에서 0 회 수행시 큐에 남는 수

1. 1회 수행한 요세푸스 수열 \(j(n, k)_1\) 은 \(j(n-1, k)_0\) 과 일대일 대응이 성립한다.
2. 두 수열 간의 변환은 k 를 더하고 모듈로 연산을 하는 간단한 식으로 정의할 수 있다.
3. 그러므로 요세푸스 수열 \(j(1, k)_0\) 부터 변환을 반복하면 \(j(n, k)_0\) 의 마지막 항이 된다.

자세한 것은 위키 를 살펴보자. 의외로 나무위키 에도 잘 설명되어 있다.

시간 복잡도

O(\(\mathrm{N}\))

코드

int main()
{
	int n, k;
	cin >> n >> k;

	int r = 1;
	for (int i = 1; i <= n; i++)
		r = (r + k - 1) % i+1;
	cout << r;
}

큰 N 에 대한 joseph

조금만 더 생각하면 일대일 대응하는 수열을 적절히 선택해 변환식을 유추할 수 있으면 다양한 점화식을 만들어 낼 수 있다는 걸 알 수 있다. 이를 활용한 점화식 중 하나가 n 에 비해 k 가 매우 작은 경우이다. 이는 SO를 보면 페이스북 해커톤의 기출문제로도 나왔다고 한다. 비슷한 문제가 Boj 에 있으며 이것을 풀어보자.

1 2 3 4 5 6 7 8 9 10  // (10, 3) 에서 0 회 수행
1 2   4 5   7 8   10  // (10, 3) 에서 3 회 수행 
2 3   4 5   6 7    1  //  (7, 3) 에서 0 회 수행

1 2 3 4 5 6 7 8   // (8, 3) 에서 0 회 수행
1 2   4 5   7 8   // (8, 3) 에서 2 회 수행
3 4   5 6   1 2   // (6, 3) 에서 0 회 수행

n 이 매우 크기때문에 한번에 1개씩 지우는게 아니라 한줄을 훑으면서 지웠다. 그러면 위처럼 나타낼 수 있다.

이에 대한 변환식은 다양한 접근으로 구할 수 있다. 나는 0회 수행한 수열에서 기본적으로 n / k * k 를 더하고, 특정 간격마다 일정한 간격으로 커지는 수를 더하면 된다는 것을 이용하였다. 이를 코드로 나타내면 다음과 같다.

시간복잡도

위키 등을 보면 O(\(k\log_{\mathrm{N}}\)) 가 된다고 한다.

• 내가 계산하기엔 O(\(\log_{k+1}{N}\)) 이 나오던데 이상할 따름이다.나는 \(n_{m} = n_{m+1} - n_{m+1}/k\) 를 풀어서 \(n_{m+1} = \cfrac{k-1}{k} n_{m}\) 의 점화식을 구했다. 그리고 이를 변형해 \((\cfrac{k-1}{k})^N = 1\) 을 만족하는 \(N\) 을 구하면 될거라 생각했는데 뭔가 다른가보다.

코드

using ll = long long;

ll Joseph(ll n, ll k)
{
	if (n == 1) return 1;
	ll r = 1;
	if (n <= k) {
		for (int i = 1; i <= n; i++)
			r = (r + k - 1) % i + 1;
		return r;
	}
	r = Joseph(n - n / k, k);
	ll offset = n / k * k;
	ll st = n - offset;
	if (r < st + k) return (r + offset - 1) % n + 1;
	return ( r + offset + (r - st - 1) / (k - 1) - 1 ) % n + 1;
}

int main()
{
	ll n, k;
	cin >> n >> k;
	if (k == 1) cout << n;
	else cout << Joseph(n, k);
}