백준 10802 : 369 게임

문제 링크

두 수 a,b가 주어지고, 두 수 사이의 3의 배수이거나 숫자에 3,6,9중 하나라도 들어있는 수의 개수를 찾는 문제이다. 언듯 보면 굉장히 쉬운 문제인거 같지만, 이 문제의 특징은 무려 a와 b가 최대 10^100000이라는 것이다. 완전탐색의 ㅇ도 생각해볼 수 없는 값이다.

따라서 문제를 해결할 때, 3의 배수의 개수 + 3,6,9가 포함된 수의 개수 - 교집합으로 해결할까 생각했지만, 교집합을 구하는 것이 생각보다 까다로워 보였고, 따라서 3,6,9가 포함되지 않은 3의 배수의 개수 + 3,6,9가 포함된 수의 개수를 구하기로 생각했다. 또한 a~b까지의 개수를 구하기 위해서 lessthanX함수를 정의해서 0~X-1까지 박수의 갯수를 구하는 함수를 만든 후 lessthanX(b) - lessthanX(a) + isclap(b)를 구함으로써 해결하려고 하였다. isclap함수는 그 수가 박수를 치는 수인지 판단해주는 함수이다.

3의 배수인 수의 특징은 수들의 각 자릿수 숫자들을 모두 더하면 3의 배수가 된다는 것이다. 따라서 이 성질을 이용해서 dp테이블을 만들어, dp[i][m] = 3,6,9 를 사용하지 않고 길이 i짜리 수를 만들었을 때 나머지가 m이 되는 수의 개수로 정의했다. 그 다음 X의 가장 큰 자릿수부터 계산을 시작하는데, X의 길이를 n이라고 할 때, 가장 큰 자릿수의 숫자가 5라는 것은 가장 큰 자릿수가 0~4일 때는 나머지 수가 0~10^n-1까지 될 수 있다는 것이고, 여기서 가장 큰 자릿수 + 나머지 수의 자릿수의 합 = 3의배수가 되도록 dp테이블을 이용해서 더해주면 된다. 그 다음 자릿수를 점점 줄여가면서 계산을 해주면 된다.

말이 조금 장황한데, 지금 쉽게 구할 수 있는건 자릿수가 i일 때, 나머지가 m이 되는 수의 개수이다. 따라서, 예를 들어 575311이라는 수가 주어졌을 때, 가장 큰 자릿수의 숫자를 고정시킨 후에(0~4) dp값을 이용해서 더해주고, 그 다음 자릿수를 볼 때에는 가장 큰 자리를 5로 고정해주고, 그 다음 자리를 고정시키고(0~6) 같은 과정을 반복해주는 것이다. 이 때, 자릿수에 3또는 6또는 9가 있으면, 다음에 그 수를 고정시키면 3,6,9가 이미 수에 포함되므로 반복문을 빠져나온다. 반복문을 한번 돌릴때 커버하는 수의 범위를 생각해보면 이해가 좀 더 쉬울 것이다.

그 다음 이제 구해야하는 것은 X보다 작은 3,6,9가 포함된 수의 개수이다. 이 것은 전체 수의 개수에서 3,6,9가 포함되지 않는 수를 뺌으로써 계산할 수 있다. 이번에는 dp[i] = 길이 i의 3,6,9를 사용하지 않고 만들수 있는 수의 개수 로 정의한 다음, 이전에 3의 배수의 개수를 계산했던 것처럼 계산해주면 된다. 가장 큰 자릿수부터 고정해가면서 dp테이블을 이용해서 더해주면 된다.

이해가 안되는 부분이 있으면 댓글로 남겨주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21*1e8;
const int MAX = 1e5;
const int mod = 20150523;

vector<vector<int>> dp;
vector<int> ex;

int lessthanX(const string& num)
{
    int ret = -1;
    int n = num.size();
    
    int cur = 0;
    for(int i = 0;i<n;i++)
    {
        int top = (num[i] - '0');

        for(int j = 0;j<top;j++)
        {
            if(j != 0 && j % 3 == 0) continue;

            int temp = (cur + j) % 3;
            ret += dp[n-i-1][(3-temp) % 3];
            ret %= mod;
        }

        if(top != 0 && top % 3 == 0) break;
        cur = (cur + top) % 3;
    }
    
    int ex3 = 0;

    for(int i = 0;i<n;i++)
    {
        int top = (num[i] - '0');

        for(int j = 0;j<top;j++)
        {
            if(j != 0 && j % 3 == 0) continue;

            ex3 += ex[n-i-1];
            ex3 %= mod;
        }
        
        if(top != 0 && top % 3 == 0) break;
    }

    int pow =1;
    int all = 0;

    for(int i = n-1;i>=0;i--)
    {
        all += (num[i] - '0') * pow;
        all %= mod;
        pow = (pow * 10) % mod;
    }

    cout<<num<<"->";
    cout<<ret<<" "<<all<<" "<<ex3<<endl;

    all -= ex3;
    all %= mod;
    if(all < 0) all += mod;

    return (all + ret) % mod;
}

bool isclap(const string& num)
{
    int sum = 0;
    int n = num.size();
    for(int i = 0;i<n;i++)
    {
        sum += (num[i] - '0');
        if(num[i] != '0' && num[i] % 3 == 0) return true;
    }

    return sum % 3 == 0;
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    dp = vector<vector<int>>(MAX+1,vector<int>(3,0));
    ex = vector<int>(MAX+1,0);
    
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 3;
    dp[1][2] = 3;
    ex[1] = 7;
    ex[0] = 1;

    for(int i = 2;i<=MAX;i++)
    {
        dp[i][0] = (dp[i-1][2] * 3 + dp[i-1][1] * 3 + dp[i-1][0]) % mod;
        dp[i][1] = (dp[i-1][2] * 3 + dp[i-1][0] * 3 + dp[i-1][1]) % mod;
        dp[i][2] = (dp[i-1][2] + dp[i-1][0]*3 + dp[i-1][1]*3) % mod;        

        ex[i] = (ex[i-1] * 7) % mod;
    }
 
    string a,b;
    cin>>a>>b;
	
	int ans = lessthanX(b) - lessthanX(a) + isclap(b);
	ans %= mod;
	if(ans < 0) ans += mod;
    cout<<ans;

    return 0;
}