(Elice / DP / C++) 병정들의 369 게임

병정들의 369 게임

카드 병정들은 쉬는 시간에 휴게실에 둘러앉아 369 게임을 즐기곤 합니다. 369 게임은 다음과 같은 규칙을 가지고 있습니다.

• 병정들이 양의 정수 A에서 시작하여 차례대로 돌아가면서 숫자를 하나씩 증가하면서 불러나갑니다. 단, 부르는 숫자가 3의 배수이거나 그 숫자에 3, 6, 9가 하나라도 들어 있는 경우에 숫자는 부르지 않고 손뼉을 칩니다.

예를 들어, 369 게임을 17부터 시작하는 경우에 박수를 X로 표현한다면, 이 게임의 진행은 17-X-X-20-X-22-X-X-25–X–X-28-X-X …와 같습니다.

시작하는 양의 정수 A와 끝나는 양의 정수 B가 주어졌을 때, 손뼉을 치는 총 횟수를 구하는 프로그램을 작성하세요.

 

지시사항

입력

• 한 줄에 시작하는 양의 정수 A와 끝나는 양의 정수 B를 공백으로 구분하여 입력합니다.

                                                   (1≤A≤B≤1,000,000,000)

출력

• 손뼉 치는 총 횟수를 20,200,301로 나눈 나머지를 출력합니다.

입력 예시

1 12

출력 예시

4

소스 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=20200301;

int memo[100001][3][2][2];

int dp(const string &s, int x, int sum, bool f, bool over)
{
    if(s[x]==0){
        return (f || sum==0);
    }
    if(memo[x][sum][f][over]!=-1){ return memo[x][sum][f][over]; }
    memo[x][sum][f][over]=0;
    if(over==1){
        for(char i='0'; i<=s[x]; i++){
            int val=i-'0';
            memo[x][sum][f][over]=(memo[x][sum][f][over]+dp(s, x+1, (sum+val)%3, f||(val%3==0 && val!=0), i==s[x]))%mod;
        }
    }
    else{
        for(char i='0'; i<='9'; i++){
            int val=i-'0';
            memo[x][sum][f][over]=(memo[x][sum][f][over]+dp(s, x+1, (sum+val)%3, f||(val%3==0 && val!=0), 0))%mod;
        }
    }
    return memo[x][sum][f][over];
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string a, b;
    cin >> a >> b;
    memset(memo, -1, sizeof(memo));
    int ans=dp(b, 0, 0, 0, 1);
    memset(memo, -1, sizeof(memo));
    ans-=dp(a, 0, 0, 0, 1);
    int sum=0, f=0;
    for(int i=0; i<a.size(); i++){
        sum=(sum+a[i]-'0')%3;
        f=f||(a[i]-'0'!=0 && (a[i]-'0')%3==0);
    }
    ans+=(sum==0 || f);
    cout << (ans+mod)%mod << "\n";
    return 0;
}