Ezreal 여눈부터 가네 ㅈㅈ C++ - 백준

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

dp 문제.

문제 접근

15의 배수는 5의 배수이면서 3의 배수이다.

5의 배수는 일의 자리수가 0 또는 5로 끝나야하며,

3의 배수는 모든 자리수의 합이 3의 배수여야 한다.

따라서 다음과 같은 점화식을 얻을 수 있다.

1로 끝나는 수의 점화식을 $DP_o(i,remainder)$

(두번째 인자는 3으로 나눈 나머지)

5로 끝나는 수의 점화식을 $DP_f(i,remainder)$라고 할때

$DP_o(i,0)=DP_f(i-1,2)+DP_o(i-1,2)$
$DP_o(i,1)=DP_f(i-1,0)+DP_o(i-1,0)$
$DP_o(i,2)=DP_f(i-1,1)+DP_o(i-1,1)$
$DP_f(i,0)=DP_f(i-1,1)+DP_o(i-1,1)$
$DP_f(i,1)=DP_f(i-1,2)+DP_o(i-1,2)$
$DP_f(i,2)=DP_f(i-1,0)+DP_o(i-1,0)$

이 중 답은 $DP_f(i,0)$으로 나타낼 수 있다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int n;
ll o[1515][3]={0,};
ll f[1515][3]={0,};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    o[0][1]=1; f[0][2]=1;
    cin >> n;
    for(int i=1;i<n;i++){
        o[i][0]=(f[i-1][2]+o[i-1][2])%MOD;
        o[i][1]=(f[i-1][0]+o[i-1][0])%MOD;
        o[i][2]=(f[i-1][1]+o[i-1][1])%MOD;
        f[i][0]=(f[i-1][1]+o[i-1][1])%MOD;
        f[i][1]=(f[i-1][2]+o[i-1][2])%MOD;
        f[i][2]=(f[i-1][0]+o[i-1][0])%MOD;
    }
    cout << f[n-1][0];
    return 0;
}