[BaekJoon/C] No.1081 : 합

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

 

소스코드 & 문제풀이

 

1부터 n까지의 모든 자릿수를 순회하며 각 숫자가 각 자릿수에서 등장한 횟수를 계산합니다.

반복문에서는 자릿수를 단계적으로 증가시키면서(1 → 10 → 100 등) 계산

 

sum(b)에서 sum(a-1)을 빼서 a부터 b까지의 자릿수 합을 계산합니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 특정 숫자 범위(1부터 n까지)의 모든 자릿수의 합을 계산하는 함수
long long sum(long long n)
{
    // n이 0 이하일 경우 합은 0
    if (n <= 0) return 0;

    // 각 숫자(0~9)의 자릿수별 등장 횟수를 저장할 배열
    long long c[10] = { 0, };
    long long s = 1; // 현재 자릿수를 나타내는 변수 (1의 자리, 10의 자리, 100의 자리 등)
    long long sum = 0; // 최종 결과값
    long long t, r; // t는 몫, r은 나머지 계산에 사용

    // n이 0보다 클 때까지 반복
    while (n > 0)
    {
        t = n / (s * 10); // 현재 자릿수를 기준으로 몫 계산
        r = n % (s * 10); // 현재 자릿수를 기준으로 나머지 계산

        // 각 숫자의 자릿수 등장 횟수 계산
        for (int i = 0; i < 10; i++)
            c[i] += t * s; // 현재 자릿수 이전까지의 모든 숫자가 s번씩 등장

        // 현재 자릿수에서 등장 횟수 추가
        for (int i = 1; i <= r / s; i++)
            c[i] += s; // 현재 자릿수에서 숫자가 등장한 횟수를 추가

        // 현재 자릿수에서 남은 부분(r % s) 처리
        c[(r / s + 1) % 10] += r % s;

        // n에서 현재 자릿수 처리 후, 다음 자릿수로 이동
        n -= 9 * s;
        s *= 10; // 자릿수를 다음 단계로 변경
    }

    // 숫자 1~9의 자릿수 합을 계산
    for (int i = 1; i < 10; i++)
        sum += i * c[i]; // 숫자 i가 등장한 횟수에 i를 곱해 합산

    return sum; // 최종 결과 반환
}

int main()
{
    long long a, b; // 범위의 시작과 끝을 저장할 변수
    // 두 정수 a와 b를 입력받음
    scanf("%lld%lld", &a, &b);

    // b까지의 자릿수 합에서 (a-1)까지의 자릿수 합을 뺌
    printf("%lld\n", sum(b) - sum(a - 1));

    return 0; // 프로그램 종료
}

 

예제 입출력 결과