[백준 14650] 걷다보니 신천역 삼 (small)

간단한 dp문제이다.

3의 배수는 각 자리의 합이 3의 배수이다.

dp[i][j] 는 i의 자릿수 중 모든 자릿수를 더한 뒤 3으로 나눈 나머지가 j가 되는 수의 경우의 수

#include <iostream>
using namespace std;
 
 
int main(void) {
    int n;
    int dp[1005][3];
    cin >> n;
 
    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[1][2] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
        }
    }
 
    cout << dp[n][0] << endl;
}