백준 11025 요세푸스 문제 3

 

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

11025번: 요세푸스 문제 3

요세푸스 문제는 큐를 이용하여 풀어도 되고, dp를 이용해도 되고, 재귀식을 이용해 풀어도 됩니다.

하지만 현재 문제의 메모리가 매우 제한적이므로, 큐나 dp 등 큰 메모리를 사용하는 것을 사용할 수는 없고, 재귀를 이용하여도, 스택에 function call 메모리가 계속 쌓이므로 사용이 안 됩니다.

따라서 기존 요세푸스 문제 점화식을 loop로 풀어서 적용하면 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    // 메모리 아주 작으니 loop로 변경
    // f(0,k) = 0, f(n,k) = (f(n-1,k) + k -1 mod n) + 1
    int f = 0;
    for(int i = 1; i <= n; i++) {
        f = (f+k-1) % i + 1;
    }
    cout << f;
}