[BOJ] 5696. 숫자 세기

문제

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

5696번: 숫자 세기

 

풀이

$x,y$가 input으로 들어올때, $f(x)=$(1부터 $x$까지 적었을 때, 나타나는 0~9의 숫자의 배열)이라고 정의하자.

그럼 구하고자 하는 정답은 $f(y)-f(x-1)$이 된다.

 

그럼 $f(x)$는 어떻게 구할까?

자릿수별로 각 숫자의 개수를 계산한다는 아이디어를 기본적으로 생각해보자.

즉, 1의 개수를 셀때, 1의 자리에 오는 1, 10의 자리에 오는 1, 100의 자리에 오는 1,....들을 모두 세서 더해준다면 구하고자하는 전체 1의 개수를 구할 수 있을 것이다.

 

결국 위의 질문은 1~x까지의 숫자중 $10^t$자리가 $a$인 숫자가 모두 몇개인지를 각 $t$에 대해 모두 풀어서 더해주면 된다.

이는 다음과 같이 경우를 나누어 풀수 있다.

case 1) $a$가 $x$의 $10^t$자리 숫자보다 작을 경우

예를 들어서 $x=12345, a=1, 10^t=100$인 경우를 보자.

그러면 ??1?? 꼴의 숫자가 몇 개인지를 세는 것인데, 이는 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류) * 100이 된다.

또한 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류)는 위의 예시에서는 0부터 12까지이므로, 총 13개가 가능하다.

즉 1??, 11??, 21??, 31??, ... , 121??의 경우가 가능하다는 뜻이다.

수식으로 나타내면 $(x/10^{t+1}+1)\times 10^t$가지 경우임을 알 수 있다.

 

case 2) $a$가 $x$의 $10^t$자리 숫자와 같을 경우

$x=12345, a=3, 10^t=100$을 예로 들어보자.

이 경우에는 3??, 13??, ..., 113??까지는 자유롭게 가능하고, 123??의 경우에는 0~45까지 총 46개만 가능하다.

같은 방식으로 수식으로 나타내면 $(x/10^{t+1})\times 10^t+(x%10^t)+1$ 가지 경우가 있음을 알 수 있다.

 

case 3) $a$가 $x$의 $10^t$자리 숫자보다 클 경우

비슷한 방식으로  $x=12345, a=5, 10^t=100$을 예로 들어보자.

이 경우에는 5??, 15??, ..., 115??까지만 가능하므로 case 1)의 경우보자 $10^t$개 적게 된다.

따라서 이 경우는 $(x/10^{t+1})\times 10^t$ 가지이다.

 

따라서 이를 모두 각각 더해주면 된다.

주의할 점은 맨 앞자리에 0이 올수는 없으므로 0은 각 경우에서 $10^t$개만큼 빼주어야 한다는 점이다.

즉 10?? 꼴의 숫자는 있지만, 0?? 꼴의 숫자는 존재하지 않으므로, 이 경우를 빼주는 것이다.

 

위와 같은 방식으로 0~9까지 등장수를 모두 더해주면 $f(x)$를 구할 수 있다.

 

Time Complexity : $O(logx+logy)$

 

코드

#include<iostream>
#include<vector>
using namespace std;

vector<int> f(int t)
{
	vector<int> ret(10);
	for(int i=1;i<=t;i*=10)
	{
		for(int j=0;j<10;j++)
		{
			if( j<(t/i)%10) ret[j] += (t/(i*10)+1)*i;
			else if( j==(t/i)%10 ) ret[j] += (t/(i*10))*i+(t%i)+1;
			else ret[j] += (t/(i*10))*i;
		}
		ret[0]-=i;
	}
	return ret;
}
int main() {
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0 && y==0)break;
		vector<int> a1 = f(y);
		vector<int> a2 = f(x-1);
		for(int i=0;i<10;i++)
		{
			cout<<a1[i]-a2[i]<<" ";
		}
		cout<<"\n";
	}
}