11025 - 요세푸스 문제 3

step 1

메모리 제한이 16mb입니다. 이거는 배열이나 세그 트리 같은 것을 사용하지 않고 풀라는 이야기입니다.

(N, K)-요세푸스 순열의 답을 알고 있다고 해봅시다. (N+1, K)-요세푸스 순열은 무엇일까요?

step 2

예시에 있는 경우를 생각해 봅시다. 한 사람이 제거될 때 까지 진행한 다음 순서와 숫자를 조금 섞어주면 다음과 같이 됩니다.

(6, 3) 요세푸스 순열의 답은 1입니다. 그럼 이 과정을 반대로 올라간다고 생각하면 (7,3) 요세푸스 순열은 4임을 알 수 있습니다.

(1, K) 요세푸스 순열의 답은 1입니다. 여기서부터 거꾸로 올라가면서 생각하면 쉽게 답을 구할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
int main() {
    int n, m, i,po=1;
    scanf("%d%d", &n, &m);
    for (i = 2;i <= n;i++) {
        int mm = m%i;
        if (mm == 0) mm = i;
        if (i - mm >= po) po += mm;
        else po -= i - mm;
    }
    printf("%d", po);
    return 0;
}