백준 20500 (Ezreal 여눈부터 가네 ㅈㅈ)

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

20500번: Ezreal 여눈부터 가네 ㅈㅈ

1과 5로만 이루어진 수 중에서 15로 나누어 떨어지는 수가 몇 개있는지 세보자

1자리

1
5

X

2자리

15 O
55
11
51

1가지

이렇게 하다가 알 수 있는 간단한 사실
15 = 3*5

따라서 15의 배수이려면 k*(3*5) 이어야 하고, 5로 나누어 떨어져야 15로 나누어 떨어진다.

그러므로 1의 자리 수가 1이라면 불가능 끝에는 5만 올 수 있다.


여기서부터 조금 막혔다.

근데 10^N은 15로 나누었을때 나머지가 10이며
5*10^N은 15로 나누었을때 나머지가 5였다.

9876을 k로 나눈 나머지는

(a+b+c+d)%k = (a%k + b%k + c%k + d%k)%k 이므로

나머지가 0,5,10인 갯수를 저장해두고 dp식을 짜면 된다.

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
const int MAX = 1005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

int dp[2000][3];


int main() {
    FASTIO
    int N;
    cin >> N;
    dp[2][0] = 1;
    dp[2][2] = 1;
    for(int i=3; i<=N; i++){
        dp[i][0] = (dp[i-1][1]+dp[i-1][2])%MOD;
        dp[i][1] = (dp[i-1][0] + dp[i-1][1])%MOD;
        dp[i][2] = (dp[i-1][0] + dp[i-1][2])%MOD;
    }
    cout << dp[N][0];
}