BOJ 12873 기념품

기념품
(http://boj.kr/12873)

링크드리스트를 이용해 $t^3$만큼 뒤로 가서 지워도 되지만, 점화식을 찾을 수 있다.

$n$명이 있을 때는 $1^3$번째 사람이 제외된다. 그 후에, $n-1$명이 남았을 때 아까 제외된 사람부터 출발한다.
즉, $n$명이 있을 때의 결과는 $n-1$명이 있을 때 $1$번부터 시작한 결과와 같다.
마찬가지로 $n-1$명이 있을때의 결과는 $n-2$명이 있을 때 $1^3+2^3$번부터 시작한 결과이다.

식으로 나타내면, $i$명이 있을 때의 결과를 $D_i$라고 했을 때,
$D_1=1,$
$D_i = (D_{i-1} + (n-i+1)^3 - 1) \bmod i + 1$이다.

식이 좀 복잡해보이는데, $-1$과 $+1$은 인덱스가 $1$부터 시작하기 때문에 나머지 연산을 고려해 넣어준 것이고,
$(n-i+1)^3$은 $i$명이 남았을 때 넘어가는 횟수이다.

#include <bits/stdc++.h>
 
int d[5001];
 
int main() {
    int n;
 
    scanf("%d", &n);
 
    for (int i = 2;i <= n;++i)
        d[i] = (d[i - 1] + (n - i + 1) * (n - i + 1) % i * (n - i + 1)) % i;
 
    printf("%d", d[n] + 1);
 
    return 0;
}