Compy's Blog
480 words
2 minutes
[BOJ] 숫자 세기
2025-06-05

숫자 세기

TimeLimitMemoryLimitConditionTAG
1s128MB(1 ≤ A ≤ B ≤ 108)Implementation, Math

그냥 0~9까지의 숫자가 현재 자리에서 얼마나 반복되는지 더하는 것을 주어진 A, B에 맞춰서 둘 다 구해주고 빼버리면 그 사이에 있는 값을 알 수 있어요!

정답 코드
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>

#define mod 1000000007LL

using namespace std;
using ll = long long;
int n, m;

vector<ll> solution(ll n) {
    vector<ll> cnt(10, 0);
    if (n < 0) return cnt;
    
    ll place = 1;
    ll lower = 0;
    ll current, higher;
    
    while (n / place > 0) {
        current = (n / place) % 10; // 앞을 본다
        higher = n / (place * 10); // 앞앞을 본다 - 이정도는 무조건 돌아가니까 내가 현재위 factor로 가리키고 있는 현재의 나는 어차피 돌면서 무조건 앞앞의 개수만큼 나오니까 바로 곱해버리기. 근데 잠시만
    // 그러면 매번 올라갈대마다 그 위치의 값을 곱해버리는건데 이게 맞을까?
        // 왜 이게 맞게 나오지 잠시만 뭐지
        // 아니 난 빡대가린가 방금까지 생각하던걸 까먹고 이상한데서 고뇌에 빠지네 ㅂㅅ
        // 아니 당연히 현재 위치가 반복되는 횟수를 곱한건데 어 왜 다 곱하는거지 ㅇㅈㄹ
        // 진자 기억력 요즘 문제 심각하다. 제발 고치자 제발 좀 제발 거의 금붕어 느낌이다
        
        // 변수 이름을 느낌있게 바꾸자
        for (int i = 0; i < 10; i++) {
            cnt[i] += higher * place;
            
            if (i < current) cnt[i] += place;
            else if (i == current) cnt[i] += lower + 1;
            
            if (i == 0) cnt[i] -= place;
        }
        
        lower = n % (place * 10);
        place *= 10;
    }
    
    return cnt;
}

int main() {
    ll A, B;
    
    while (cin >> A >> B) {
        if (A == 0 && B == 0) break;
        vector<ll> cntB = solution(B);
        vector<ll> cntA = solution(A - 1);
        
        for (int i = 0; i < 10; i++) cout << cntB[i] - cntA[i] << " ";
        cout << "\n";
    }
    
    return 0;
}
[BOJ] 숫자 세기
https://compy07.github.io/Blog/posts/boj/5696/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-06-05