취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1179번 문제인 마지막 요세푸스 문제이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1179 

Josephus problem의 점화식을 모른다면 11025번 문제를 먼저 풀어보자.

글쓴이는 이 글에 풀이 코드를 작성해두었다.

위 글의 점화식에서, 많은 횟수의 연산은 mod값을 취하나 취하지 않나 그 결과가 동일할 것이라는 것을 관찰하자.

따라서, mod값을 취해야 할 때가 될 때까지 N을 한번에 올리는 것을 반복하는 것으로 이 문제의 시간복잡도 개선을 시도할 수 있다.

한 바퀴에 K명씩 건너뛰면서 사람을 제거한다면, 한 바퀴에 대략 전체의 1/K에 해당하는 사람들이 제거될 것이다. 이것이 몇번 반복되어야, 즉 몇 바퀴 돌아야 과정이 끝나는지는 (1-1/K)의 거듭제곱을 이용하여 예상할 수 있다. 이 한바퀴 도는 것과, 위에서 mod값을 취해야 할 때가 될 때까지 N을 한번에 올리는 연산의 횟수는 같다는 점에 주목하자. 또한, 이 문제의 K의 제한이 굉장히 작아, 이 연산의 횟수가 충분히 적어질 것이라는 점을 확인하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N, K; cin >> N >> K;
	
	ll ans = 0;
	ll NN = 1;
	if (K == 1) cout << N;
	else {
		while (1) {
			ll x = (NN - ans - 1) / (K - 1) + 1;
			if (NN + x > N) {
				ans += (N - NN) * K;
				break;
			}
			ans = (ans + K * x) % (NN + x);
			NN += x;
		}

		cout << ans + 1;
	}
}