[BAE/<JOON> 문제풀이] 1081. 합

https://www.acmicpc.net/problem/1081

1081번: 합

핵심::
책페이지와 동일한 숫자 갯수 카운팅 알고리즘 사용

풀이::
책페이지 알고리즘을 사용해 각자리 숫자의 출현 횟수를 구하고
각 숫자를 곱해 합을 구한다.

L부터 U까지의 합이 필요하므로 S(U) - S(L - 1)를 구하면 된다.

의견::
책페이지랑 사실상 같은 문젠데 왜 이게 1티어 더 낮은지 모르겠음

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
using ull = long long;

struct bk { int front, back, x, p; };

ull getcount(int n, const vector<bk>& var) {
    ull sum = 0;
    for (int i = 0; i < var.size(); i++) {
        int fxp = pow(10, var[i].p);
        if (var[i].x > n) {
            // 현재 자리의 숫자가 정산하는 숫자를 포함하는 경우 
            sum += (var[i].front + 1) * fxp;
        }
        else if (var[i].x == n) {
            // 현재 자리의 숫자가 정산하는 숫자와 같은 경우
            sum += var[i].front * fxp + (var[i].back + 1);
        }
        else if (var[i].x < n) {
            // 현재 자리의 숫자가 정산하는 숫자를 포함하지 않는 경우 
            sum += var[i].front * fxp;
        }
    }
    return sum;
}

int main() {    
    int n, m; cin >> n >> m;
    vector<int> arr, srr;
    int j = n - 1;    
    while (j > 0) {
        arr.push_back(j % 10);
        j /= 10;
    }
    j = m;
    while (j > 0) {
        srr.push_back(j % 10);
        j /= 10;
    }

    vector<bk> vls(arr.size()), vle(srr.size());

    for (int i = 0; i < arr.size(); i++) {
        vls[i].p = i;
        vls[i].x = arr[i];
        int sum = 0;
        for (int j = i - 1; j >= 0; j--) {
            sum *= 10;
            sum += arr[j];
        }
        vls[i].back = sum;
        sum = 0;
        for (int j = arr.size() - 1; j >= i + 1; j--) {
            sum *= 10;
            sum += arr[j];
        }
        vls[i].front = sum;
    }    

    for (int i = 0; i < srr.size(); i++) {
        vle[i].p = i;
        vle[i].x = srr[i];
        int sum = 0;
        for (int j = i - 1; j >= 0; j--) {
            sum *= 10;
            sum += srr[j];
        }
        vle[i].back = sum;
        sum = 0;
        for (int j = srr.size() - 1; j >= i + 1; j--) {
            sum *= 10;
            sum += srr[j];
        }
        vle[i].front = sum;
    }
    ull sum = 0;
    for (int i = 1; i <= 9; i++) {
        sum += (getcount(i, vle) - getcount(i, vls)) * i;
    }

    cout << sum;

    return 0;
}