369 게임( BOJ 10802 )

문제 : https://www.acmicpc.net/problem/10802

10802번: 369 게임

 

문제 파악하기

369게임을 진행 하면서 특정 구간동안 몇 번의 박수를 치는지 구하는 문제입니다. 기존에는 숫자에 3, 6, 9 중 하나라도 포함된다면 박수치는 규칙에서 3의 배수이면 박수를 친다는 새로운 규칙이 추가되었습니다. 물론 반복문을 사용하면 손쉽게 구할 수 있지만 입력되는 숫자의 범위가 너무도 크기 때문에 새로운 알고리즘이 필요합니다.

 

문제 해결하기

이 문제는 결국 A ~ B 사이의 숫자 중 조건에 만족하는 숫자들의 개수를 구하는 문제입니다. 따라서 이 문제는 1부터 특정 숫자까지 조건에 만족하는 숫자의 개수를 구할 수 있다면 우리가 원하는 구간 A ~ B 사이의 값을 구할 수 있습니다. (1 ~ B)사이의 숫자 중 조건을 만족하는 숫자의 개수를 구한 다음에 (1~(A-1))사이의 숫자 중 조건을 만족하는 숫자의 개수로 빼면 됩니다. 마치 A ~ B 사이의 누적합을 구하는 방법과 비슷하게 말이죠.

 

그럼 (1~N)사이의 숫자 중 조건을 만족하는 숫자는 어떻게 구할 수 있을까요? 문제를 해결하기 위해서는 미리 몇 가지 범위에 대해 값을 구해놓아야 합니다. 그리고 미리 구해놓은 값을 토대로 특정 숫자까지 범위를 나눠서 탐색을 하면 빠르게 원하는 구간 내 조건을 만족하는 숫자의 개수를 구할 수 있습니다. 여기서 말하는 몇 가지 범위는 바로 자릿수를 의미합니다. 우리는 입력 받은 숫자의 자릿수에 따라 해당 자릿수를 가질 때, 해당 범위 내에 만족하는 숫자의 개수가 몇 개인지 먼저 구할 수 있습니다. 그렇게 계속 탐색하다보면 우리는 원하는 범위까지 갈 수 있습니다.

 

그럼 자릿수에 대한 범위를 어떻게 나눌 수 있을까요? 바로 10의 단위로 나눌 수 있습니다. 예를 들어 1부터 2215까지의 범위를 구하고 싶다고 가정해봅시다. 그럼 우리는 2215까지의 숫자를 (0 ~ 999), (1000~2215)로 나눌 수 있습니다. 그리고 (1000~2215)는 (1000~1999), (2000~2215)로 나눌 수 있으며, 이렇게 10의 단위로 나눠보면 다음과 같이 세분화되어 나타날 수 있습니다.

2215 => (1~999) + (1000~1999) + (2000~2099) + (2100~2199) + (2200~2209) + (2210~2215)

이렇게 구간을 나눈 다음, 미리 구해둔 범위 내 조건을 만족하는 숫자의 개수를 사용하면 쉽게 구할 수 있습니다. 그렇다면 이제는 미리 범위 내 조건을 만족하는 숫자의 개수를 구해봅시다. 이를 위해서는 조건을 유심히 살펴봐야 합니다. 조건에 따르면 박수를 치기 위해서는 다음 조건 중 한 가지라도 만족해야 합니다.

(1) (3, 6, 9) 중 적어도 한 가지 숫자를 포함한 숫자

(2) 3의 배수인 숫자

 

위의 조건을 토대로 우리가 구해야하는 숫자는 다음과 같이 2가지 분류로 나눌 수 있습니다.

(1) (3, 6, 9) 중 적어도 한 가지 숫자를 포함한 숫자

(2) (3, 6, 9)를 포함하지 않은 3의 배수

 

(3, 6, 9)를 포함한 숫자 중에는 3의 배수가 있을 수 있고, 반대로 3의 배수 중에는 (3, 6, 9)를 포함하지 않은 숫자가 있습니다. 그렇기에 우리는 2개의 분류에 포함된 숫자를 각각 구해야합니다. 그럼 처음에는 (1)번 조건을 만족하는 숫자의 개수를 구해봅시다. 방법은 바로 각 숫자의 최상단 숫자와 자릿수를 사용하면 배열에 한번에 저장할 수 있습니다. 다음 숫자를 살펴봅시다.

2 _ _ _

위 숫자는 2000~2999 사이의 숫자를 의미합니다. 그럼 위 숫자 사이에서 (3, 6, 9) 중 적어도 한 가지 숫자를 포함하는 숫자의 개수는 몇 개일까요? 바로 (0 ~ 999) 사이의 숫자 중 (3, 6, 9)를 하나라도 포함하는 숫자의 개수와 동일합니다. 그럼 이번에는 다음 숫자를 살펴봅시다.

3 _ _ _

이번에는 조금은 쉬워졌습니다. 3 아래에 (0~999)사이의 숫자 중 어떤 숫자가 들어와도 조건을 만족하기 때문입니다. 이를 통해 우리는 조건에 따라 점화식을 세울 수 있다는 걸 알게 되었습니다. DP369[idx][num]을 (idx)자리 숫자이며, 최상단 숫자가 num일 때, (3,6,9)를 포함하는 숫자의 개수라고 정의하면, 다음과 같은 점화식을 만들 수 있습니다.

DP369[idx][num] = 10^(idx-1) (num=3, 6, 9)

DP369[idx][num] = DP369[idx-1][0]+...+DP369[idx-1][9] (num=1,2,4,5,7,8)

 

이렇게 점화식을 세우면 100,000자리의 숫자라도 1부터 현재 숫자까지의 총 박수 횟수를 구할 수 있습니다. 그럼 이번에는 (3, 6, 9)를 포함하지 않은 3의 배수의 개수를 구해보도록 합시다. (3, 6, 9)를 포함하지 않은 3의 배수 역시 마찬가지로 점화식을 통해 구할 수 있습니다. 다만, 최상단 숫자가 (3, 6, 9)일 경우에는 0이 되며, 나머지 숫자의 경우 3으로 나눴을 때 나오는 모든 경우에 대해 구해주어야 합니다.

DP3[idx][num][0] = DP[idx][1] = DP[idx][2] = 0 (j=3, 6, 9)

DP3[idx][0] = tot3[idx-1][0]

 

이렇게 범위마다 조건을 만족하는 모든 숫자의 개수를 구해놓으면 남은 일은 입력받은 숫자의 범위를 나누는 것입니다. 범위를 나눌 때에 중요한 점은 범위를 점차 좁혀가야한다는 점입니다. 범위를 좁힌다는 건, 한 번에 확인하는 숫자의 범위가 점점 좁아지는 것을 의미하며, 마지막에는 숫자 1개씩 확인하면서 탐색이 마무리되어야 합니다. 그럼 예시를 통해 알아보도록 하겠습니다. 만약 2114라는 숫자를 입력받았다면 우리는 다음과 같이 범위를 나눌 수 있습니다.

2114 >> (1~999) + (1000~1999) + (2000~2099) + (2100~2109) + (2110~2114)

 

1부터 2114까지의 숫자를 위와 같이 3자리 > 2자리 > 1자리 순서로 나누어서 볼 수 있습니다. 이렇게 나눈 다음에 DP369배열과 DP3 배열에 저장된 값을 적절하게 확인하면 문제를 해결할 수 있습니다.

 

소스코드

#include <iostream>
#include <string>
#define NMAX 100010
#define MOD 20150523
#define lint long long int
using namespace std;
 
string A, B;
 
lint num369[NMAX][10], tot369[NMAX];
lint mul3[NMAX][10][3], tot3[NMAX][3];
 
lint cntA, cntB;
 
// 거듭제곱
lint pow(lint val, int k) {
    if(k == 0) return 1;
    else if(k == 1) return val;
    else {
        if(k%2 == 0) return pow(( val*val )%MOD, k/2);
        else return ( val*pow(val*val%MOD, k/2) )%MOD;
    }
}
 
// 박수 횟수 구하기
lint get(string num) {
    lint ret, len;
 
    ret = 0;
    len = num.length();
 
    // 3, 6, 9가 포함된 숫자 카운트
    // Ex. 4237 >> (0000~3999) + (4000~4199) + (4200~4229) + (4230~4237)
    for(int idx=0, l=len;idx<len;idx++, l--) {
 
        // 예시: 4237
        // 현재 자릿수 이전 자릿수까지 박수 카운트 >> 000~999
        if(num[idx] > '0') ret = (ret + tot369[l-1]%MOD);
 
        // 현재 최대 자릿수 이전까지 박수 카운트 >> (1000~1999) + (2000~2999)
        int t = num[idx]-'0';
        for(int j=1;j<t;j++) ret = (ret + num369[l][j])%MOD;
 
 
        // 3, 6, 9가 포함된 경우, 남은 숫자 모조리 더하기
        if(num[idx] == '3' or num[idx] == '6' or num[idx] == '9') {
            // Ex. 3297에서 3000 카운트하기
            ret++;
 
            // 뒤에 있는 모든 숫자 더해서 결괏값에 반영
            lint t=0;
            for(int nxt =idx+1;nxt<len;nxt++) t = (t*10 + (num[nxt]-'0'))%MOD;
 
            ret = (ret + t)%MOD;
 
            // 탐색 종료
            break;
        }
    }
 
 
    // 3, 6, 9가 포함되지 않은 3의 배수 카운트
    int before=0;
    for(int idx=0, l=len;idx<len;idx++, l--) {
        // before: 이전까지 나온 숫자들의 합
        // m: 3의 배수를 만족하기 위해 필요한 값. Ex) before가 1일 때, m은 2
        int m = (3-before)%3;
 
        // 현재 자릿수 숫자가 0인 경우 스킵
        if(num[idx] == '0') {
            // 대신, 3의 배수이면서 10의 배수인 경우 카운트 Ex) 4200인 경우, 1 카운트
            if(m == 0 and idx+1 == len) ret++;
            else continue;
        }
 
        else {
            // 예시: 4237
            // 현재 숫자 이전 자릿수까지 카운트 >> 000~999
            ret = (ret + tot3[l-1][m])%MOD;
 
            // 현재 숫자 이전까지 카운트(단, 마지막 자리인 경우 끝까지 탐색)
            // Ex. 4237에서 현재 2인 경우) 4000~4199까지 탐색
            //     4237에서 현재 7인 경우) 0~7까지 모두 탐색
            int t = num[idx]-'0';
            if(idx+1 == len) t++;
 
            for(int j=1;j<t;j++) ret = (ret + mul3[l][j][m])%MOD;
 
            // 다음 탐색을 위한 갱신 및 점검
            before = (before+t)%3;
 
            // 현재 숫자가 3, 6, 9라면 조건(3, 6, 9를 포함하지 않는 3의 배수)를 만족하지 않기에 탐색 종료
            if(num[idx] == '3' or num[idx] == '6' or num[idx] == '9') break;
        }
    }
 
    return ret;
}
 
int check(string num) {
    // A가 박수쳐야 하는지 확인
    int f, tmp;
 
    f = tmp = 0;
    for(int i=0;i<num.length();i++) {
        if(num[i]=='3' or num[i]=='6' or num[i]=='9') {
            f = 1;
            break;
        }
        else tmp += (num[i]-'0');
    }
 
    if(f or tmp%3==0) return 1;
    else return 0;
}
 
int main() {
    // init
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    // input
    cin >> A >> B;
 
    // 3, 6, 9가 포함된 숫자 구하기
    // num369[idx][j]: 자릿수가 idx이며, 맨 앞자리 숫자가 j일 때 박수치는 총 횟수
    tot369[1] = 3;
    num369[1][3] = num369[1][6] = num369[1][9] = 1;
    for(int idx=2;idx<=B.length();idx++) {
        for(int j= 0;j<=9;j++) {
            if(j>0 and j%3 == 0) num369[idx][j] = pow(10, idx-1);
            else num369[idx][j] = tot369[idx-1];
 
            tot369[idx] = (tot369[idx] + num369[idx][j])%MOD;
        }
    }
 
    // 3, 6, 9가 포함되지 않은 3의 배수 구하기
    // mul3[idx][j][k]: 자릿수가 idx이며, 맨 앞자리 숫자가 j이고, 3으로 나눴을 때 나머지가 k인 숫자의 개수
    tot3[0][0] = 1;
    for(int idx=1;idx<=B.length();idx++) {
        if(idx == 1) {
            for(int j=0;j<=9;j++) {
                if(j>0 and j%3 == 0) continue;
                else {
                    mul3[idx][j][j%3]++;
                    tot3[idx][j%3]++;
                }
            }
        }
 
        else {
            // 초깃값
            for(int k=0;k<3;k++) tot3[idx][k] = 0;
 
            for(int j=0;j<=9;j++) {
                // 3, 6, 9 제외
                if(j>0 and j%3 == 0) continue;
 
                for(int k=0;k< 3;k++) {
                    mul3[idx][j][k] = tot3[idx-1][(k-j + 12)%3];
 
                    tot3[idx][k] = (tot3[idx][k] + mul3[idx][j][k])%MOD;
                }
 
            }
        }
    }
 
    // A와 B까지 박수의 총합 구하기
    // check(num): num 숫자 확인하기
    // cntA: 0 ~ (A-1)까지 총 박수 횟수 / cntB: 1 ~ B까지 총 박수 횟수
    cntA = (get(A) - check(A) + MOD)%MOD;
    cntB = (get(B) + MOD)%MOD;
 
 
    cout << (cntB-cntA+MOD)%MOD;
 
}
 
/*
300 400
ans: 100
 
399 400
ans: 1
*/

후기

기본적인 아이디어는 금방 떠올렸지만 실제로 구현하는데 시간이 걸린 문제입니다. 특히 420와 같이 10의 배수이자 3의 배수인 숫자로 끝날 경우에는 한번 더해주어야 한다는 케이스까지 떠올리는데 시간이 좀 걸렸습니다. 그렇지만 특별한 자료구조를 사용하지 않고 배열만으로 문제를 풀 수 있기에 DP의 매력을 느낄 수 있는 문제라고 생각합니다.