백준 1019번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	플래티넘 5

---

풀이

밀린 문제 정리하기의 첫 단추를 끼울 문제이다. 이 문제는 사실 알고리즘이라기보단 수학적인 규칙을 찾는 문제에 가까웠다. 아는 지인이 이걸 풀었길래 나도 시도해봤다가 며칠동안 고민했던 문제이다. 이 문제를 이해하기 위해 예제를 하나씩 분석해보자. 예제입력 2부터 보자. 입력이 7이다. 페이지를 나열하면 다음과 같을 것이다.

1, 2, 3, 4, 5, 6, 7

1~7까지 모두 1번씩 나왔기 때문에 답은 

0 1 1 1 1 1 1 1 0 0

이 될 것이다. 여기까지만 보면 잘 모르겠다.

 

예제입력 3을 보자. 입력은 19이다. 나열해보면

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

이다. 우선 한자리 숫자만 보면 1부터 9까지 모두 한번씩 등장했다. 또한, 두자리 숫자들에서도 일의 자리에 1~9가 모두 한번씩 등장했다. 

이제 10의 자리를 보자. 1이 10번 등장한다. 또한 10으로 인해 0도 하나 등장한다. 따라서 답은

1 12 2 2 2 2 2 2 2 2

이 되는 것이다.

 

다른 입력을 넣어보자. 248은 어떨까?

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ..., 98, 99, 100..., 247, 248

우선 1의 자리에만 보자. 0은 10~240으로 인해 24번 등장한다. 1~239 범위 안에서 1~9가 모두 24번씩 등장한다. 또한 240~248에서 1~8이 추가적으로 한번 더 등장한다. 다음으로 10의 자리를 보면 0은 100~109, 200~209으로 20번 등장한다. 10~239에서 1~3은 30번씩, 4는 29번씩, 5~9는 20번씩 등장한다. 마지막으로 100의 자리를 보면 1은 100번, 2는 49번 등장한다.

 

따라서 답은 

44 155 104 55 54 45 45 45 45 44 

이 된다.

 

실제 숫자를 사용하니 계산과정이 복잡하다. 계산과정을 일반화를 해보며 내가 사용한 전략을 풀어보겠다. 우선 이 문제를 숫자 하나하나씩 다 세보면서 어떤 숫자가 나왔는지 세는건 주어진 시간복잡도 안에서 당연히 불가능하다. 해당 방법은 기본적으로 O(N + logN!)의 시간복잡도를 가질 것이다. 1부터 N까지 각 숫자에 대해 자릿수들을 모두 살펴봐야 하고, 어떤 자연수 k의 자릿수는 logk+1이기 때문에 이를 1부터 n까지 모두 확인하면 다음과 같은 식이 나온다.

logN!은 스털링 근사로 인해 NlogN-N으로 근사한다.

 

확실한건 N의 최댓값이 10^9인 시점에서 숫자가 조금만 커져도 안될거 같다는건 알겠다. 이 문제를 풀기위해선 아무리 최악이어도 O(logN)에 가깝게 풀이를 만들어낼 필요는 있어보인다. 모든 숫자를 세로로 써보자. 적당히 n=43까지만 써보자.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
.
.
.
39
40
41
42
43

 

줄여도 많긴 하다... 일단 1의 자리부터 보자. 1의 자리에서 1~9는 1~39의 범위에서 각각 4번씩 등장한다. 좀 더 자세히 써보면 01~39에서 각각 4번 등장함을 알 수 있다. 이는 n의 10의 자리가 4이며, 이만큼 나옴을 알 수 있다. 그 다음 0은 10, 20, 30, 40으로 이 역시 n의 10의 자리인 4만큼 나온다는것을 알 수 있다. 남은 41~43은 n을 10으로 나눈 나머지인 1~3까지는 한번씩 더 나옴을 알 수 있다. 또한 40~43의 10의 자리인 4는 4번이 나온다. 왜 갑자기 10의 자리를 지금 따지는지, 그것도 맨 뒤의 숫자만을 따지는지는 뒤에서 설명하겠지만, 일단을 이를 인지하고 넘어가자. 지금까지 센 0~9의 개수는 다음과 같다.

0	4
1	5
2	5
3	5
4	8
5	4
6	4
7	4
8	4
9	4

 

1의 자리와 맨 마지막에 나오는 10의 자리를 모두 봤으니, 1의 자리와 맨 마지막의 숫자들을 소거해도 될 것이다. 소거해보자.

1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3

 

1~9에서 1의 자리를 소거하면 아무것도 남지 않기에 지워진다. 1부터 3까지는 각각 10번 등장한다. 이후 또 소거하게 되면 아무것도 남지 않는다. 만약 이전 과정에서 자투리로 남은 4를 세지 않았다면, 다른 숫자들은 다 10번씩 등장하는데, 4만 4번인게 처리하기 귀찮아 질 것이다. 그래서 앞의 과정에서 미리 세준 후 넘어온 것이다. 최종적으로 1~3에 10을 더해주면 된다. 이러한 방법은 숫자의 길이가 길어지더라도 계속해서 반복하면 된다. 세자리숫자부터는 분량을 매우 많이 먹어 블로그에 적기에는 조금 힘들기에 생략하지만, 그때의 1의자리는 100개씩 등장하고, 또 자투리 숫자들이 등장할 것이다. 이 방식을 그대로 사용하면 된다.

 

아무리 긴 숫자가 오더라도, 1의 자리와 맨 마지막에 자투리로 남는 숫자들을 세준 후, 맨 마지막의 자투리 숫자들과 1의 자리를 모두 소거해준다. 이를 반복하고, 더해주는 숫자를 10씩 곱해주며 가중치를 주면 구해지게 된다. 이러한 방식의 시간복잡도는 n의 자릿수와 자투리 숫자의 자릿수의 곱에 영향을 받는다. 둘다 logN이기 때문에 해당 알고리즘은 O((logN)^2)의 시간복잡도를 가질 것이다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int page[10];

void count_page(int w) {
	if (n <= 0) return;

	int q = n / 10, r = n % 10;

	// 등장하는 1의 자리의 개수를 저장
	for(int i = 1; i < 10; i++) {
		page[i] += q * w;
	}

	// 마지막 1~r만큼 남는다. 해당 케이스 카운트
	for(int i = 1; i <= r; i++) {
		page[i] += w;
	}

	// 0은 q번 등장한다.
	page[0] += q * w;

	// 마지막으로 등장하는 10의 자리는 10개가 되지 않기에 전처리
	if (q) {
		int tmp = q;
		while(tmp){
			page[tmp % 10] += (r + 1) * w;
			tmp /= 10;
		}
	}
	n = q - 1;
	count_page(w * 10);
}

void sol() {
	count_page(1);
	for(int& x : page) cout << x << ' ';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	sol();
}