480 words
2 minutes
[BOJ] 숫자 세기
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
1s | 128MB | (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;
}