1, 2, 3 더하기 5

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

같은 수를 연속해서 쓰면 안된다. -> 점화식이 이차원 배열로 나옴

d[i][j] = d[i - 1][2] + d[i-1][3] + d[i - 2][1] + d[i-2][3] + d[i - 3][1] + d[i-1][2]

 

테스트 케이스마다 dp를 구하면 시간 초과가 난다!!

케이스가 크다! overlflow가 무조건 난다..

dp와 오버플로우 -> 항상 조심

테스트 케이스마다 나머지 연산을 해줘야한다

오버플로우 방지 나머지 연산

(a + b) % c = (a % c + b % c) % c      [곱셈에서도 성립]

(a / b) % c = (a * b ^ (c - 2)) % c   

(a - b) % c = (a % c - b % c + c) % c

#include <stdio.h>
long long d[1000001][4];
const long long mod = 1000000009LL;
const int limit = 100000;
int main() {
    for (int i=1; i<=limit; i++) {
        if (i-1 >= 0) {
            d[i][1] = d[i-1][2] + d[i-1][3];
            if (i == 1) {
                d[i][1] = 1;
            }
        }
        if (i-2 >= 0) {
            d[i][2] = d[i-2][1] + d[i-2][3];
            if (i == 2) {
                d[i][2] = 1;
            }
        }
        if (i-3 >= 0) {
            d[i][3] = d[i-3][1] + d[i-3][2];
            if (i == 3) {
                d[i][3] = 1;
            }
        }
        d[i][1] %= mod;
        d[i][2] %= mod;
        d[i][3] %= mod;
    }
    int t;
    scanf("%d",&t);
    while (t--) {
        int n;
        scanf("%d",&n);
        printf("%lld\n",(d[n][1] + d[n][2] + d[n][3])%mod);
    }
}