15990 : 1, 2, 3 더하기 5

풀이

계단오르기 아니면 RGB거리 문제랑 비슷하게 풀면 된다

코드

#include <cstdio>
const int m = 1e9+9;
int n, t, d[3][100001];
int main() {
    d[0][1] = d[1][2] = d[0][3] = d[1][3] = d[2][3] = 1;
    for (int i = 4; i <= 100000; i++) {
        d[0][i] = (d[1][i-1]+d[2][i-1])%m;
        d[1][i] = (d[0][i-2]+d[2][i-2])%m;
        d[2][i] = (d[0][i-3]+d[1][i-3])%m;
    }
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        printf("%lld\n", ((long long)d[0][n]+d[1][n]+d[2][n])%m);
    }
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-07 16:34

Read more posts by this author