[백준/BOJ] 1081 합

문제 : 1081번: 합

각 자리 별로 숫자를 나누어서 현재 자릿수의 숫자합을 계산하여 더하는 식으로 구하였다.

현재 자릿수를 기준으로 hi / x / lo 세 부분으로 나누면

[hi*자릿수*1~9까지의 합]+[자릿수*1~x-1까지의 합]+[x*(lo+1)]

이렇게 세 파트로 나누어 보는 것이 가능하므로 해당 방식으로

0~N까지의 합을 구해 차이를 출력하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M;
ll f(ll num){
    ll ret=0;
    vector<ll> v(1,0); // 0~9까지의 누적합 저장
    for (int i=1;i<10;i++)
        v.push_back(v[i-1]+i);
    for (ll i=1;i<=num;i*=10){
        ll hi=num/(i*10), x=(num%(i*10))/i, lo=num%i; // 현재 자릿수를 기준으로 수를 나눔
        ret+=v[9]*i*hi; // 윗부분은 1~9가 모두 등장
        if (x)
            ret+=v[x-1]*i; // x-1까지는 현재 자릿수만큼 등장
        ret+=x*(lo+1); // x는 아래수+1번만큼 등장
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    cout << f(M)-f(N-1);
    return 0;
}