[BOJ 백준] 1081번 : 합 (C++)

[BOJ 백준] 1081번 : 합 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 각 자리마다 0~9까지 올 수 있는 개수를 각각 구하기

2. 현재 자리의 수에 따라, 3구간을 나눠서 작업하기

[가정]
235의 값에서 10의 자리를 검사 중

1) 0 ~ 2 : (0~2) * (235를 100으로 나누기 + 1) * (현재 자리인 10)
2) 3 : 3 * (235를 100으로 나누기 * 현재 자리인 10 + 235를 현재 자리인 10의 나머지 + 1) 
3) 4 ~ 9 : (4~9) * (235를 100으로 나누기 * 현재 자리인 10)

즉, 위 상황을 일반화하면, 아래와 같습니다.
현재 검사하고 있는 자리 수의 값을 a라고 가정합니다.

1) 0 ~ (a-1) : (번호) * (값을 현재 검사하고 있는 자리의 하나 큰 수로 나누기 + 1) * (현재 검사하고 있는 자리)
2) a : (a) * [(값을 현재 검사하고 있는 자리의 하나 큰 수로 나누기) * (현재 검사하고 있는 자리) + (a를 사용한 개수) + (본인 1개)]
3) (a+1) ~ 9 : (번호) * (값을 현재 검사하고 있는 자리의 하나 큰 수로 나누기) * (현재 검사하고 있는 자리)

3. L과 U에 대해서 각각 구한 뒤, 뺄셈 진행

4. L을 구성하는 각 자리의 합을 따로 구해서 더하기

 

과정

235의 값이 입력되었을 때, 0~235까지의 각 자리 수의 합에 대해서 구해보겠습니다.

 

만약에, 현재 10의 자리를 검사하고 있다고 가정합니다.

먼저, 3구간으로 나눕니다.

0~2, 3, 4~9로 나눕니다.

 

 

1) 현재 기준(3) 보다 작은 경우

0~235까지 10의 자리가 1인 경우는 총 30개입니다.

 

즉, 현재 기준(3) 보다 작은 경우에는 2xx 값에서 10의 자리가 1인 경우를 모두 사용했습니다.

그러므로, 01x에서 10개, 11x에서 10개, 21x에서 10개를 사용했습니다.

따라서, 현재 검사하고 있는 자리보다 한 자리 큰 100으로 235를 나누고 +1을 한 후, 현재 검사하고 있는 자리인(10)을 곱하면 됩니다.

 

마지막으로 현재 검사하고 있는 번호를 곱합니다.

 

위와 같은 상황을 일반화하면, (번호) * (값을 현재 검사하고 있는 자리의 하나 큰 수로 나누기 + 1) * (현재 검사하고 있는 자리)이 됩니다.

 

 

2) 현재 기준(3)인 경우

0~235까지 10의 자리가 3인 경우는 총 36개입니다.

 

현재 기준(3)인 경우를 보면, 03x에서 10개, 13x에서 10개, 23x에서 6개를 사용했습니다.

따라서, 먼저 현재 검사하고 있는 자리보다 한 자리 큰 100으로 235를 나누고, 현재 검사하고 있는 자리(10)를 곱합니다.

그 후, 현재 검사하고 있는 자리(10)로 235를 나머지 연산한 값을 더합니다.

이 경우, 234까지만 반영되므로, 235까지 반영되기 위해 +1을 진행합니다.

 

마지막으로 현재 검사하고 있는 번호를 곱합니다.

 

위와 같은 상황을 일반화하면, (번호) * [(값을 현재 검사하고 있는 자리의 하나 큰 수로 나누기) * (현재 검사하고 있는 자리) + (a를 사용한 개수) + (본인 1개)]

 

 

3) 현재 기준(3) 보다 큰 경우

 

0~235까지 10의 자리가 5인 경우는 총 20개입니다.

 

현재 기준(3)인 경우를 보면, 05x에서 10개, 15x에서 10개를 사용했습니다.

따라서, 먼저 현재 검사하고 있는 자리보다 한 자리 큰 100으로 235를 나누고, 현재 검사하고 있는 자리(10)를 곱합니다.

 

마지막으로 현재 검사하고 있는 번호를 곱합니다.

 

위와 같은 상황을 일반화하면,

 

 

4) 나머지 추가 과정

 

위 과정을 통해, 1의 자리부터 가장 높은 자리까지 검사를 진행하면 됩니다.

 

그 후, 0~L과 0~U에 대해서 각 자리 수의 합을 모두 구합니다.

구한 값을 서로 빼고, L에 대한 각 자리 수의 합을 별도로 구한 뒤, 더합니다.

 

---

03. 정답 코드

// 골드 1 - 1081번 : 합
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// L <= x <= U 
// 각 자리의 합 구하기
// U -> 20억

// 165
// 1의 자리 -> 0~4 : (5개) * (17), 5 : 17개,  6~9 : (4개) * 16개
// 10의 자리 -> 0~5 : (6개)* (2개) * (10), 6 : 16개, 7~9 : (1개) * (10)
// 100의 자리 -> 1 -> 66개

// 2356
// 1의 자리 -> 0~6 : 236개, 7~9 : 235개
// 10의 자리 -> 0~4 : 24개 * (10), 5 : 230 + 7개, 6~9 : (4번) * 23개 * (10)
// 100의 자리 -> 0~2 : (3개) * 100, 3 : 200개 + 57개 , 4~9 : (2개) * 100
// 1'000의 자리 -> 0~1 : (1개) * 1000, 2 : 357개

// 14
// 1의 자리 -> 0~3 : (4번) * 2개, 4 : (1번) * 2개, 5~9 : (5번) * 1개
// 10의 자리 -> 0 : (1번) * 10개, 1 : (1번) * 4개, 

using ll = long long;

ll simulate(const ll x)
{
    ll result = 0;

    ll div = 10;

    do
    {
        ll base = x / div;

        ll cur_check = div / 10;
        ll rest = x % cur_check;

        ll mid = (x % div) / cur_check;

        for(int i = 0; i < 10; i++)
        {
            if(i < mid)
                result += (i * (base + 1) * cur_check);

            else if(mid == i)
                result += (i * (base * cur_check + rest + 1));
            
            else
                result += (i * (base * cur_check));

        }

        div *= 10;
    } while(x * 10 / div > 0);

    return result;
}

ll each(const ll x)
{
    string base = to_string(x);
    ll result = 0;
    for(const char& each : base)
        result += (ll)(each - '0');

    return result;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 최소 범위 L, 최대 범위 U
    ll L, U;
    cin >> L >> U;

    ll result = simulate(U) - simulate(L) + each(L);

    cout << result << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!