[BOJ] 14651번: 걷다보니 신천역 삼 (Large)

14651번: 걷다보니 신천역 삼 (Large)

$dp[i][j] = dp[i - 1][j] \times 3$ 이기 때문에 처음에는 코드를 이렇게 짰다.

#include <cstdio>
long long n, dp[33334][3];
const int R = 1e9 + 9;
int main()
{
    scanf("%lld", &n);
    dp[2][0] = 0, dp[2][1] = dp[2][2] = 1;
    for (int i = 3; i <= n; ++i)
        for (int j = 0; j < 3; ++j)
            dp[i][j] = (dp[i - 1][j] % R * 3) % R;
    printf("%lld\n", (dp[n][0] % R + dp[n][1] % R + dp[n][2] % R) % R);
    return 0;
}

근데 다른 분들 코드를 보니 역시나 줄일 수 있었다. 같은 작업이 중복되기 때문에 초기값인 2만 정해주면 아래와 같은 코드로 나타낼 수 있었다.

#include <cstdio>

int main()
{
    int n;
    long long s = 2;
    scanf("%d", &n);
    for (int i = 3; i <= n; ++i)
        s = s * 3 % 1000000009;
    printf("%lld", n == 1 ? 0 : s);
    return 0;
}