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;
}