학교 수업 중 과제로 똑같은 문제가 나와서 풀게 됐다.
www.slideshare.net/Baekjoon/baekjoon-online-judge-3015?next_slideshow=1
여기서 백준님 풀이를 보면
1과 n 사이가 아닌, a와 b 사이에서의 개수를 구하는걸로 문제를 바꿀 수 있다.
이때 a의 일의 자리수가 0이 될 때까지 a++,
b의 일의 자리수가 9가 될 때까지 b-- 해주고
그 과정에서 거치는 수들에 대해 각 숫자의 개수를 업데이트 해준다.
그리고 a, b 사이의 0~9의 개수는 각각
(b/10 - a/10 + 1) * digit 이다.
digit은 지금 a, b의 일의 자리수가 원래는 어느 위치였는지를 알려준다.
즉 지금 a, b의 일의 자리수의 값이 원래는 digit 자리수였다는 거다.
그리고 a/10, b/10, digit*10으로 값을 바꿔 계속 반복한다.
이때 n = 1인 경우 처럼
a++, b-- 하는 게 불가능한 경우를 체크해야 하는데
나는 a <= b인 동안만 실행되도록 while문 조건을 추가했다.
그리고 a > b이면 return하도록 한다.
이때 거치는 수들에 대해 각 숫자의 개수를 업데이트 할 때 주의할 점은
각 자리 숫자의 개수를 그냥 더하는 게 아니라 digit만큼 더해야 한다
예를 들어 a가 1 -> 10으로 바뀌었고
그 다음에 다시 a/=10으로 1이 되었다고 하자.
이때의 1의 digit은 10이기 때문에
a++ 하면서 1이 등장하는 횟수를 더해줄 때
1만 더하는 게 아니라 10을 더해야 한다.
그래야 10~19에서 1이 한 번씩 등장했던 게 모두 포함된다.
처음에 이 부분 때문에 틀렸다.
int ans[10];
void Count(int n, int digit) {
while (n) {
ans[n % 10] += digit;
n /= 10;
}
}
void Solve(int a, int b, int digit) {
while (a % 10 != 0 && a <= b) {
Count(a, digit);
a++;
}
while (b % 10 != 9 && a <= b) {
Count(b, digit);
b--;
}
if (a > b) {
return;
}
a /= 10; b /= 10;
for (int i = 0; i < 10; i++) {
ans[i] += (b - a + 1) * digit;
}
return Solve(a, b, digit * 10);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
Solve(1, n, 1);
for (int i = 0; i < 10; i++) cout << ans[i] << ' ';
cout << ENDL;
return 0;
}