문제

문제 분석

5명이 주어졌다고 가정해보자.
1번부터 누구의 선물을 받을 지 순서대로 정해보자.
5->4->2->..
4->5->2->..
이후 상황은 같기 때문에 DP로 풀 수 있지 않을까 했다.
다만, 이 경우엔 bitmask가 필요한데 10^6 명을 체크해야 해서 쉽지 않다.

여기서 막혔다.

이런 경우 진짜 아예 손으로 모든 경우를 조사해보아햐 한다.
1명인 경우, 2명인 겨우, 3명인 경우, 4명인 경우, 5명인 경우까지 수형도를 그려보았다.
잘 보니 한명을 추가할 때마다 규칙적으로 계산이 가능하다는 것을 알게 되엇다.

알고리즘

• Dynamic Programming

자료구조

• 1D DP

결과

/*
NOTE:
DP를 떠올리긴 했으나 다른 방식의 dp였고, 시공간 복잡도상 불가능했다.
막혔을 때는 결국 유치원생처럼 가장 Naive한 방법으로 문제를 해결하고, 
그 사이에 패턴과 규칙을 발견하는게 좋은 것 같다.
*/
#include <iostream>
#include <vector>
using namespace std;

const int64_t MAX_STUDENT = 1000000;

vector<int64_t> table(MAX_STUDENT+1, 0);

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    table[2] = 1;
    table[3] = 2;
    for ( int64_t stu = 4; stu <= MAX_STUDENT; stu++){
        table[stu] = ((table[stu-1] + table[stu-2])*(stu-1)) % 1000000000;
    }

    int trg = 0;
    cin >> trg;
    cout << table[trg];

    return 0;
}

Other

막혔을 땐, bruteforce보다도 더 Naive하게, 손으로 작은(시작점)부터 큰(끝)까지 손으로 적어보자. 규칙이 나올 수 있다.