[S2] 1, 2, 3 더하기 3

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

15988번: 1, 2, 3 더하기 3

당연히 동적으로 쉽게 풀리는 문제이다.

F(n) = F(n-1) + F(n-2) + F(n-3)을 동적으로 해결하면 되는 문제이다. 하지만... 엄청난 방법이 존재하게 되는데..

https://jhcard.tistory.com/63

[S5] 13301. 타일 장식물

이 문제와 비슷하다고 보면 된다.

피보나치를 O(logn)으로 확인 가능한 방법이다. 하지만, 우리는 이것과 다르다. 무려 3개가 피보나치 형태로 되어있다.

트리보나치(Tribonachi)수열이라 불린다. 트리보나치를 O(logn)으로 할 수 있는데 거기에는 행렬 멱법을 이용하는 것이다. 행렬 멱법과 트리보나치를 O(logn)을 한번에 알 수 있도록 그림으로 표현하였다.

우리는 F(2)와 F(1), F(0)을 알고 있다. 이것을 이용하여 쉽게 O(logn)에 접근하여야 한다. 코드는 다음과 같다.

#include <cstdio>

void mul(long long R[][3], long long M[][3]) {
    long long tmp[3][3]{};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                tmp[i][j] = (tmp[i][j] + R[i][k] * M[k][j]) % 1000000009;
            }
        }
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) R[i][j] = tmp[i][j];
    }
}

int main(void) {
    int T, n; scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);
        n--;
        long long R[3][3] = { 1, 0, 0, 0, 1, 0, 0, 0, 1 };
        long long M[3][3] = { 1, 1, 1, 1, 0, 0, 0, 1, 0 };

        while (n) {
            if (n & 1) mul(R, M);
            mul(M, M);
            n >>= 1;
        }
        long long Result = (R[2][0] * 4 + R[2][1] * 2 + R[2][2] * 1) % 1000000009;
        printf("%lld\n", Result);
    }
}

mul함수가 행렬의 곱을 해주는 부분이다.

 

이외에도 동적으로 푸는 코드는 다음과 같다.

#include <cstdio>

int main(void) {
    int T, n, dp[1000001]{ 0, 1, 2, 4 }, idx = 4; scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);

        for (;idx <= n; idx++) {
            dp[idx] = (1L * dp[idx - 1] + dp[idx - 2] + dp[idx - 3]) % 1000000009;
        }
        printf("%d\n", dp[n]);
    }
}