[BOJ] 선물 전달 - Compy's Blog

선물 전달

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 ≤ N ≤ 1,000,000)	Dynamic Programming

음.. 제가 한번 풀고서 갑자기 하나가 구상하던게 떠올라서 또 제출해봤더니 그것도 정답이더라구요?

음.. 제가 작성한 코드 2개가 같은 의미를 지닌건 아닌거 같은데.. 그냥 나열해서 관찰한 후에 규칙성 찾아서 풀었습니다..

그냥 열심히 머리 굴리면 되긴하는데.. 뭔가 수학적으로 딱 구해서 해보는 날이 오면 좋겠네요..

풀이 영상

정답 코드

1번

#include <iostream>
#include <vector>
#include <algorithm>

#define mod 1000000000

using namespace std;
using ll = long long;



ll dp[1'000'001];

int main() {
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 9;
    dp[5] = 44;
    
    int n;
    cin >> n;
    
    for(ll i = 6; i <= n; i++){
        dp[i] = ((i-1)*dp[i-1] + (i-1)*dp[i-2]) % mod; // ㄹㅇ 이거라고?
        
    }
    cout << dp[n];
    return 0;
}

/*
 a               0
 a b             1
 a b c           2 -> 2*1 + 0
 a b c d         9 -> 3*2(6) + 3 * 1
 a b c d e      44 -> 4*9(36) + 4 * 2(8) = 44 ㄹㅇ 이건가
 a b c d e f   ???
 
 
  
 */

2번 (요놈 왜..)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
ll dp[1000001];

int main() {
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 9;
    

    int n;
    cin >> n;
    
    bool check = false;
    for(ll i = 5; i <= n; i++){
        dp[i] = i * dp[i-1];
        if(check) dp[i]++;
        else dp[i]--;
        dp[i]%= 1000000000LL;
        check = !check;
    }
    
    cout << dp[n] ;
    return 0;
}