1081 - 합

문제 링크: https://www.boj.kr/1081 

1081번: 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	2016	390	328	36.203%

문제

L보다 크거나 같고, U보다 작거나 같은 모드 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

10 14

예제 출력 1

15

C++ code

#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;

ll f(int x)
{
	vector<int> a(10, 0);
    
    int left = 1;
    int right = x;
    int base = 1;
    
    while (left <= right)
    {
    	while(right % 10 != 9 && left <= right)
        {
        	int temp = right;
            while (temp)
            {
            	a[temp % 10] += base;
                temp /= 10;
            }
            right--;
        }
        
        if (right < left)
        	break;
        
        while (left % 10 != 0 && left <= right)
        {
        	int tmp = left;
            while (tmp)
            {
            	a[tmp % 10] += base;
                tmp /= 10;
            }
            left++;
        }
        
        left /= 10;
        right /= 10;
        
        for (int i = 0; i < 10; i++)
        	a[i] += (right - left + 1) * base;
        
        base *= 10;
    }
    
    ll ret = 0;
    for (int i = 0; i <= 9; i++)
    	ret += (a[i]*i);
    
    return ret;
}

int main(void)
{
	int lower, upper;
    scanf("%d %d", &lower, &upper);
    
    printf("%lld", f(upper)-f(lower-1));
    return 0;
}