백준 / 1019 책 페이지 C++

www.acmicpc.net/problem/1019

1019번: 책 페이지

페이지가 n인 책에서 0~9가 몇 번 나오는지 구하는 문제입니다.

( 책은 1페이지부터 시작, n<=1,000,000,000 ) 

 

n이 1,000,000,000 (10억) 이하이므로 한 페이지씩 다 구하면 시간초과입니다. 

그렇기 때문에 n보다 작은 수 중 일의 자리가 9인 가장 큰 수를 구한 뒤, 100,....00 ~ (구한 수) 까지 1의 자리를 보면, 

0~9가 (구한 수/10 - 100...00/10 + 1) 개 존재합니다. 이를 10, 100자리를 반복합니다. (100...000은 n보다 작은 수 중 10의 거듭제곱인 수 중 가장 큰 수)

 

각 자리의 배열을 count[10]라 합시다.

 

예를 들어, n=9876 이라고 하면, 1000 ~ 9876의 수를 먼저 살펴봅니다.

9876보다 작은 수 중 1의 자리가 9인 가장 큰 수는 9869입니다. 그러므로 1000~9869 까지는 1의 자리에 0~9가

(986-100+1) 개 존재함을 알 수 있습니다. 그러므로 count[0]~count[9]를 (986-100+1) 만큼 더해줍니다.

그리고 9870~9876은 6개 밖에 없으므로 그냥 구해줍니다. 

 

그 다음으로 9869/10 = 986을 살펴봅니다. 986보다 작은 수 중 1의 자리가 9인 가장 큰 수는 979입니다.

그러므로 100~979를 살펴보면, 1의 자리에 0~9가 (97-10+1) 번 나타나고, 이는 원래 수의 10의 자리에 해당하는 녀석들이므로, count[0]~count[9]에 (98-10+1)*10 만큼 더해줍니다.

그리고 980~986 또한 각 자리 별로 10씩 더해줍니다.

 

그 다음으로 979/10=97보다 작은 수 중 1의 자리가 9인 가장 작은 수는 89입니다.

그러므로 10~89까지 1의 자리에 0~9가 (8-1+1)번 나타나고, 원래 수의 100의 자리에 해당하는 녀석들이므로, 

count[0]~count[9]에 (8-1+1)*100 만큼 더해줍니다.

그리고 90~99 또한 각 자리 별로 100씩 더해줍니다.

 

마지막으로 89/10=8보다 작은 수 중 1의 자리가 9인 가장 작은 수는 -9인데 이는 불가능한 경우이므로, 한 자리 수가 남았을 경우 그냥 더해줍니다. 원래 수의 1000의 자리에 해당하므로 count[1]~count[8] 에 1000씩 더해줍니다.

 

이제 1000 보다 작은 값에 대해서 구하면 되는데 이는 n=999인 경우와 동일하므로 n이 한 자리 수가 될 때까지 돌리면 됩니다.

 

다만, 101과 같은 경우, 101보다 작은 수 중 1의 자리가 9인 가장 큰 수는 99이고, 101보다 작은 수 중 10의 거듭제곱인 가장 큰 수는 100인데, 100>99 이므로 이러한 경우는 따로 구해줍니다.

100,101 을 따로 구한 뒤, 99를 n으로 생각하여 풀면됩니다.

 

코드는 다음과 같습니다.

(실제로 찍어보니 1,000,000,000을 대입해도 count[0]~count[9]가 int 범위를 안 넘으므로 그냥 int로 해도 됩니다.)

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;

int n;
long long cnt[10];

// num보다 작은 수 중 1의 자리 9인 것중 가장 큰 수
int LastIsNine(int num) {
	while (1)
	{
		if (num % 10 == 9)
			break;
		num--;
	}
	return num;
}

// A < B
// A는 B보다 작은 수 중 10의 거듭제곱 꼴인 가장 큰 수
// ex) B=9876 => A=1000
// digit : 자릿수 (1의 자리, 10의 자리,...)
void AtoB(int A, int B, int digit)
{
	// 한 자리수만 남았을 경우
	if (B < 10) {
		for (int i = A; i <= B; i++)
			cnt[i] += (long long)digit;
		return;
	}

	int tmp = LastIsNine(B); // B보다 작은 값중 일의 자리가 9인 가장 큰 수

	// tmp+1부터 B까지 애들 다 구하기
	for (int i = tmp + 1; i <= B; i++) {
		string s = to_string(i);
		for (int j = 0; j < s.size(); j++) {
			int idx = s[j] - '0';
			cnt[idx] += (long long)digit;
		}
	}

	// A부터 tmp까지 구하기
	for (int i = 0; i < 10; i++) {
		cnt[i] += (long long)((tmp / 10 - A / 10 + 1) * digit);
	}

	// 나머지 부분 계산
	AtoB(A / 10, tmp / 10, digit * 10);
	return;
}

int main()
{
	cin >> n;
	memset(cnt, 0, sizeof(cnt));

	// n이 10이하인 경우 따로 체크 (무한루프 돌게 됨)
	if (n < 10) {
		for (int i = 1; i <= n; i++)
			cnt[i] += 1;
		for (int i = 0; i < 10; i++)
			cout << cnt[i] << ' ';
		return 0;
	}

	int len = to_string(n).size(); // n의 길이
	int A = (int)pow(10, len - 1); // A는 위에서 말한 것처럼

	// n=101 같은 경우, 99가 n보다 작은 수 중 1의 자리가 9인 것 중 가장 큰 수
	// 이런 경우는 따로 체크
	if (A > LastIsNine(n)) {

		// 100...00 ~ n까지 계산
		for (int i = LastIsNine(n) + 1; i <= n; i++) {
			string s = to_string(i);
			for (int j = 0; j < s.size(); j++) {
				int idx = s[j] - '0';
				cnt[idx] += 1;
			}
		}

		// 나머지 부분 계산
		A /= 10;
		AtoB(A, LastIsNine(n), 1);
		while (1) {
			if (A == 1)
				break;
			AtoB(A / 10, A - 1, 1);
			A /= 10;
		}
	}

	// 위가 아닌 경우 그냥 계산
	else {
		AtoB(A, n, 1);
		while (1) {
			if (A == 1)
				break;
			AtoB(A / 10, A - 1, 1);
			A /= 10;
		}
	}

	for (int i = 0; i < 10; i++) {
		cout << cnt[i] << ' ';
	}
}