BOJ 24970

https://www.mermaidchart.com/app/projects/b8bc56ca-b5b3-4dc2-9137-aa3be043e4fc/diagrams/11270193-0de6-4267-8d33-3312122fddb8/version/v0.1/edit

Mermaid Chart - Create complex, visual diagrams with text. A smarter way of creating diagrams.

 

균형 수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

1024 MB

68

35

24

58.537%

문제

처음 ⌈K/2⌉ 자리의 합과 마지막 ⌈K/2⌉ 자리의 합이 같은 길이가 K인 양의 정수를 균형 수라고 한다. ⌈x⌉는 x보다 크거나 같은 가장 작은 정수를 의미한다. 예를 들어, ⌈π⌉ = 4, ⌈5⌉ = 5이다.

12321는 처음 ⌈5/2⌉ 자리의 합이 1 + 2 + 3 = 6, 마지막 ⌈5/2⌉ 자리의 합이 3 + 2 + 1 = 6으로 서로 같기 때문에, 균형 수이다. 13722도 1 + 3 + 7 = 7 + 2 + 2 이기 때문에 균형 수이다.

T(n)은 10n보다 작거나 같은 모든 균형 수의 합이다. T(1) = 45, T(2) = 540, T(5) = 334795890 이다. N이 주어졌을때, T(N)을 출력해보자.

입력

첫째 줄에 양의 정수 N이 주어진다.

출력

첫째 줄에 T(N)을 315로 나눈 나머지를 출력한다.

제한

• 1 ≤ N ≤ 100

예제 입력 1 복사

1

예제 출력 1 복사

45

예제 입력 2 복사

2

예제 출력 2 복사

540

예제 입력 3 복사

5

예제 출력 3 복사

4771029

예제 입력 4 복사

100

예제 출력 4 복사

10453080

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

 

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 14348907; // 모듈러 연산에 사용할 소수

// 모듈러 곱셈 연산을 위한 함수들
ll ModMul(ll a, ll b) { return a * b % MOD; }
ll ModMul(ll a, ll b, ll c) { return ModMul(ModMul(a, b), c); }
ll ModMul(ll a, ll b, ll c, ll d) { return ModMul(ModMul(a, b), ModMul(c, d)); }

// 모듈러 덧셈 연산을 위한 함수
void ModAdd(ll &a, const ll b) { a += b; if(a >= MOD) a -= MOD; }

ll powerOfTen[55] = {1}; // powerOfTen[i] = 10^i를 저장하는 배열

// 동적 프로그래밍을 위한 배열들
ll numCount[51][500][10][10], numSum[51][500][10][10]; // [길이][숫자합][시작숫자][끝숫자]
ll countTotal[51][500], countNoLeadingZero[51][500];      // [길이][숫자합]
ll sumTotal[51][500], sumNoLeadingZero[51][500];          // [길이][숫자합]

// 주어진 길이에 대한 균형 수의 합을 계산하는 함수
ll calculateBalancedSum(int length) {
    ll result = 0;
    if(length == 1) return 45; // 1자리 수의 경우 1부터 9까지의 합
    if(length % 2 == 0) {
        int halfLength = length / 2;
        for(int digitSum = 0; digitSum < halfLength * 10; digitSum++) {
            // 짝수 길이의 경우:
            // 1. 앞쪽 절반의 합 * 뒤쪽 절반의 개수 * 10^halfLength
            ModAdd(result, ModMul(sumNoLeadingZero[halfLength][digitSum], countTotal[halfLength][digitSum], powerOfTen[halfLength]));
            // 2. 뒤쪽 절반의 합 * 앞쪽 절반의 개수 (선행 0 제외)
            ModAdd(result, ModMul(sumTotal[halfLength][digitSum], countNoLeadingZero[halfLength][digitSum]));
        }
    } else {
        int halfLength = length / 2;
        for(int digitSum = 0; digitSum < halfLength * 10; digitSum++) {
            // 홀수 길이의 경우:
            // 1. 앞쪽 절반의 합 * 뒤쪽 절반의 개수 * 10 * 10^(halfLength+1)
            ModAdd(result, ModMul(sumNoLeadingZero[halfLength][digitSum], countTotal[halfLength][digitSum], 10, powerOfTen[halfLength+1]));
            // 2. 중간 숫자의 합 (0~9의 합 = 45) * 양쪽 절반의 개수 * 10^halfLength
            ModAdd(result, ModMul(countTotal[halfLength][digitSum], countNoLeadingZero[halfLength][digitSum], 45, powerOfTen[halfLength]));
            // 3. 뒤쪽 절반의 합 * 앞쪽 절반의 개수 (선행 0 제외) * 10
            ModAdd(result, ModMul(sumTotal[halfLength][digitSum], countNoLeadingZero[halfLength][digitSum], 10));
        }
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    
    // 10의 거듭제곱 계산
    for(int i = 1; i < 55; i++) powerOfTen[i] = ModMul(powerOfTen[i-1], 10);
    
    // 초기 조건 설정
    numCount[0][0][0][0] = countTotal[0][0] = 1;
    for(int digit = 0; digit < 10; digit++) {
        numCount[1][digit][digit][digit] = countTotal[1][digit] = countNoLeadingZero[1][digit] = 1;
        numSum[1][digit][digit][digit] = sumTotal[1][digit] = sumNoLeadingZero[1][digit] = digit;
    }
    countNoLeadingZero[1][0] = 0; // 1자리 수에서 0은 선행 0으로 취급
    
    // 동적 프로그래밍으로 배열 채우기
    for(int len = 2; len <= 50; len++) {
        for(int digitSum = 0; digitSum < len * 10; digitSum++) {
            for(int startDigit = 0; startDigit < 10; startDigit++) {
                for(int endDigit = 0; endDigit < 10; endDigit++) {
                    ll &currentCount = numCount[len][digitSum][startDigit][endDigit];
                    ll &currentSum = numSum[len][digitSum][startDigit][endDigit];
                    for(int prevEndDigit = 0; prevEndDigit < 10; prevEndDigit++) {
                        if(digitSum >= endDigit) {
                            ll prevCount = numCount[len-1][digitSum-endDigit][startDigit][prevEndDigit];
                            currentCount += prevCount;
                            currentSum += ModMul(numSum[len-1][digitSum-endDigit][startDigit][prevEndDigit], 10) + ModMul(prevCount, endDigit);
                        }
                    }
                    currentCount %= MOD;
                    currentSum %= MOD;
                    ModAdd(countTotal[len][digitSum], currentCount);
                    ModAdd(sumTotal[len][digitSum], currentSum);
                    if(startDigit) { // 선행 0이 아닌 경우만 처리
                        ModAdd(countNoLeadingZero[len][digitSum], currentCount);
                        ModAdd(sumNoLeadingZero[len][digitSum], currentSum);
                    }
                }
            }
        }
    }
    
    ll N, totalBalancedSum = 0;
    cin >> N;
    // 1부터 N까지의 모든 길이에 대해 균형 수의 합 계산
    for(int len = 1; len <= N; len++) ModAdd(totalBalancedSum, calculateBalancedSum(len));
    cout << totalBalancedSum << endl;
}