Algorithm

문제 바로가기
전체 소스코드 보기

문제

옛날에는 책을 만들 때, 한글자 한글자를 나눠서 활자를 만들어서 그걸 합쳐서 책을 만들었다고 한다. 예를 들면 가나다라는 글씨를 쓰기 위해서는 3개의 활자가 필요할 것이다. 그렇다고 할 때, N이하의 자연수를 활자로 표현하기 위해서는 몇 개의 활자가 필요한지 구하여라.

예를 들어 10이하의 자연수를 활자로 표현하려면 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0 이렇게 11개의 활자가 필요할 것이다.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)이 주어진다.

출력

첫째 줄에 필요한 활자의 수를 1234567로 나눈 나머지를 출력한다.

풀이

해당 문제는 1 ~ n 까지의 각 자리의 갯수를 더하는 문제입니다.

그럼 간단하게 1 ~ 1000 까지의 자리수를 확인해 보겠습니다.

• 1~9 : (9 - 1 + 1) * 1 = 9
• 10 ~ 99 : (99 - 10 + 1) * 2 = 180
• 100 ~ 999 : (999 - 100 + 1) * 3 = 2700
• 1000 ~ 1000 : (1000 - 1000 + 1) * 4 = 4

즉 자리수가 같은 범위의 합은 a ~ b : (b - a + 1) * 자릿수가 됩니다.
이것을 코드로 표현하면 아래와 같습니다.

#include <iostream>

using namespace std;

int modular(int a, long b){
    return (a % 1234567 + b % 1234567) % 1234567;
}

int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long n, ans = 0, digit = 1;
    cin >> n;

    for(int cnt = 1; n >= digit; ++cnt, digit *= 10)
        ans = modular(ans, cnt * ((n >= digit*10 ? digit*10 : n + 1) -  digit));

    cout << ans << '\n';
    return 0;
}

나머지 연선의 경우 모듈러 법칙을 이용한 함수로 구현하였습니다.