백준 5425번 자리합

문제 링크입니다: https://www.acmicpc.net/problem/5425

O(b-a) 시간복잡도는 너무 오래 걸리기 때문에 DP로 접근해야합니다.

Digit DP라고 하는 다이나믹 프로그래밍 기법을 사용하면 풀 수 있는 문제였습니다.

DIgit DP의 시간복잡도는 O(10 * idx * sum * tight)이기 때문에 시간 내에 충분히 풀 수 있습니다.

자세한 내용은, https://www.geeksforgeeks.org/digit-dp-introduction/을 참고하시면 됩니다!

코드에 주석을 작성했기 때문에 이해가 가실 것입니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

long long cache[16][150][2]; //idx, sum, tight

//idx: 현재 자릿수

//sum: 숫자의 각 자리수 합

//tight ? 0 ~ digit[idx]까지만 : 0 ~ 9까지 전부 더해줌

 

//역순으로 숫자의 자릿수가 벡터에 저장된다

void getDigits(long long num, vector<int> &digit)

{

        while (num)

        {

                 digit.push_back(num % 10);

                 num /= 10;

        }

}

 

long long digitSum(int idx, int sum, int tight, vector<int> &digit)

{

        //기저 사례

        if (idx == -1)

                 return sum;

 

        //tight가 설정되어있지 않고 이미 값이 저장되어있다면

        long long &temp = cache[idx][sum][tight];

        if (temp != -1 && !tight)

                 return temp;

 

        long long result = 0;

        //tight가 설정되어있는가?

        int k = tight ? digit[idx] : 9;

 

        for (int i = 0; i <= k; i++)

        {

                 //다음 인덱스 tight가 설정되어있는가?

                 int newTight = (digit[idx] == i) ? tight : 0;

                 result += digitSum(idx - 1, sum + i, newTight, digit);

        }

 

        //tight가 설정되어있지 않을 경우에만 업데이트

        if (!tight)

                 temp = result;

       

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        for (int t = 0; t < T; t++)

        {

                 long long a, b;

                 cin >> a >> b;

 

                 memset(cache, -1, sizeof(cache));

                 vector<int> aDigit, bDigit;

                 getDigits(a - 1, aDigit);

                 getDigits(b, bDigit);

 

                 cout << digitSum(bDigit.size() - 1, 0, 1, bDigit) - digitSum(aDigit.size() - 1, 0, 1, aDigit) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~