1019 - 책 페이지
본문
지민이는 전체 페이지의 수가 $N$인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 $N$ 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.
입력
첫째 줄에 $N$이 주어진다. $N$은 $1000000000$보다 작거나 같은 자연수이다.
출력
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, …, 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- $1 \leq N \leq 1000000000$ (${10}^{9}$)
풀이
그냥 수학 문제라고 봐도 무방할 것 같다. 문제를 풀 때 너무 중구난방으로 풀어서, 이 방법대로 코드를 정리하는 것은 불가능할 것 같다.
그래서, 최백준님의 설명을 보고 코드를 정리하였다. 문제를 푸는 법과 설명이 링크에 자세히 설명되어있다.
아래 풀이는 위 설명에서의 예시를 내가 이해한 방법으로 설명한 것이다. 설명에서 사용한 예시는 ($\ref{case1}$)과 같다. 원래는 시작지점 $A$가 항상 1이어야하지만, 설명에서는 이해를 쉽게 도와주기 위해 시작지점을 임의의 수로 정하고 시작하였다. 실제 문제를 풀 때에는 $A$를 1로 고정하고 문제를 풀면 된다.
\[\begin{align} \begin{cases} A = 12345 \\B = 81742 \end{cases} \end{align} \label{case1} \tag{1}\]각 숫자가 몇번 나오는지 쉽게 계산하기 위해서는, 먼저 시작지점 $A$의 1의 자리 수를 0으로, 도착지점 $B$의 1의 자리 수를 9로 맞추는 과정을 거쳐야 한다고 이야기하였다. 만약 ($\ref{case2}$)와 같은 상황이라면, 이 사이에 등장하는 수는 그 아래 있는 수와 같다.
\[\begin{align} \begin{cases} A = 10 \\ B = 39 \end{cases} \end{align} \label{case2} \tag{2}\]- 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
- 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
- 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
$A$와 $B$ 사이에는 위와 같은 수가 존재한다. 1의 자리에 있는 굵은 숫자만 봤을 때, 각 자리수가 총 3번 반복되는 것을 알 수 있다. 이것은 ‘$B$의 10의 자리 수 $-$ $A$의 10의 자리 수 $+$ 1’ 임을 찾아볼 수 있다. 숫자 범위 안의 개수를 셀 때 쓰는 방법으로 계산할 수 있다. 이렇게 각 지점의 1의 자리 수를 고정하면 각 숫자가 몇번 나오는지 쉽게 계산할 수 있다.
그럼 1의 자리를 어떻게 고정할까? 다시 ($ \ref{case1}$)로 돌아와서, 각 자리수를 고정하자. 먼저 $A$부터 보면, $A$의 1의 자리 수를 0으로 만들기 위해서는 $A$를 12340 또는 12350으로 만들어야 한다. $[A, B]$ 범위 안에 있는 것은 12350이므로, $A=12350$으로 만들어 범위를 $[12350, B]$로 만들고, 범위 밖으로 빠진 12345, 12346, 12347, 12348, 12349에 대해서는 따로 계산을 하는 것이 쉬울 것이다. 마찬가지로, $B$의 1의 자리 수도 9로 만들 것이고, 그 값은 81739가 되어야 함을 알 수 있다. 범위 밖으로 빠진 수는 아래 코드를 이용하여 계산할 수 있다. 숫자의 각 자릿수는 10으로 나눈 나머지라는 점을 이용한다.
1
2
3
4
5
6
7
void calc(int x) {
while (x > 0) {
result[x % 10] += 1;
x /= 10;
}
return;
}
이렇게 되면 ($\ref{case1}$)의 case를 ($\ref{case3}$)으로 변형할 수 있다.
\[\begin{align} \begin{cases} A = 12350 \\B = 81739 \end{cases} \end{align} \label{case3} \tag{3}\]\(\begin{align} \text{빠진 숫자 : } 12345, 12346, 12347, 12348, 12349, 81742, 81741, 81740 \end{align}\) 빠진 숫자는 따로 calc 함수를 통해 자릿수를 추가하고, $[A, B]$ 범위의 1의 자리 수들을 미리 모두 기록하자. ($\ref{case2}$)에서 했던 대로, 각 수들은 총 $8173-1235+1$번 반복되어 나타날 것이다. 이건 따로 기록해두자.
1의 자리의 연산이 끝났다면 다음으로는 10의 자리 수가 몇번 나타나는지 계산할 필요가 있다. 그러기 위해서는 ($\ref{case3}$)의 현재 상황을 1의 자리 수를 날린 ($\ref{case4}$)로 변환하자.
\[\begin{align} \begin{cases} A = 1235 \\B = 8173 \end{cases} \end{align} \label{case4} \tag{4}\]이 상황은 ($\ref{case1}$)이랑 상황이 유사하다. 이 상황도 이전과 똑같이 조절하여 ($\ref{case3}$)의 상황과 같이 만들어주자.
\[\begin{align} \begin{cases} A = 1240 \\B = 8169 \end{cases} \end{align} \label{case5} \tag{5}\] \[\begin{align} \text{빠진 숫자 : } 1235, 1236, 1237, 1238, 1239, 8173, 8172, 8171, 8170 \end{align}\]빠진 숫자들은 역시 calc 함수를 통해 자릿수를 추가할 수 있다. 그런데 이 때 기존과 다른 점을 생각해야한다. 현재 존재하는 빠진 숫자를 우리는 지금 1235, 1236 등으로 표시하고 있지만, 이 숫자들은 사실 12350, 12360 등 1의 자리가 생략되어있다는 점이다. 1의 자리가 생략되어있다는 것은 1235라는 숫자가 $[12350, 12359]$ 까지의 숫자를 압축하고 있다는 것이고, 이것은 각 숫자가 총 10번 반복되어 나타날 것이라는 의미이다. 따라서 위의 calc 함수를 그냥 사용하면 안되고, 자릿수를 고려하며 더해줘야 할 필요성이 존재한다는 것을 의미한다. 따라서 calc 함수를 아래와 같이 수정한다. 여기서 d는 자릿수를 의미한다.
1
2
3
4
5
6
7
void calc(int x) {
while (x > 0) {
result[x % 10] += d;
x /= 10;
}
return;
}
그렇다면 ($\ref{case5}$)에서도 ($\ref{case3}$)과 같은 방식으로 1의 자리 수를 모두 계산하려고 시도할 때, 사실 ($\ref{case5}$)에 있는 1의 자리들은 사실 10의 자리 수이므로, 계산 결과에 10을 곱해야 한다는 사실을 눈치챌 수 있을 것이다.
모든 예시가 끝났다. 위 예시를 이용하여 일반화하면 아래와 같이 작성할 수 있다.
- 시작지점 $A$와 도착지점 $B$을 정한다.
- $A$와 $B$가 같아질 때까지 반복한다. ( 둘이 같다는 것은 둘 사이의 수가 더이상 존재하지 않음을 의미한다. )
- $A$의 1의 자리 수를 0으로, $B$의 1의 자리 수를 9로 조절한다.
- $A$에 1씩 더해가며 범위를 조절한다. 범위 밖으로 빠진 수는
calc를 통해 자릿수를 계산한다. - $B$에 1씩 빼가며 범위를 조절한다. 범위 밖으로 빠진 수는
calc를 통해 자릿수를 계산한다.
- $A$에 1씩 더해가며 범위를 조절한다. 범위 밖으로 빠진 수는
- $A$와 $B$ 사이의 1의 자리 수의 개수를 모두 계산한다. 계산 식은 ‘($B$의 10의 자리 수 $-$ $A$의 10의 자리 수 $+$ 1) $\times$ 현재 계산 중인 자릿수(
d)’이다. - $A$와 $B$의 1의 자리 수를 제거한다. 현재 계산 중인 자릿수
d의 단위를 증가시킨다.
- $A$의 1의 자리 수를 0으로, $B$의 1의 자리 수를 9로 조절한다.
- $A$의 자릿수를
calc를 통해 계산한다. ( 둘 사이의 수가 존재하지 않는 것이지, 그 수가 존재하지 않는 것은 아니므로 결과에 추가해야한다. )
위 일반화를 이용하여 해답을 계산할 수 있다. 원래 문제에서는 시작지점 $A$를 1로 고정함에 유의하여 문제를 해결하자.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#define DECIMAL 10
int result[DECIMAL];
int n;
int d = 1; // number of digit
int s = 0; // start
void calc(int x) {
while (x > 0) {
result[x % 10] += d;
x /= 10;
}
return;
}
int main() {
scanf("%d", &n);
// make subproblem
while (s < n) {
if (s == 0 || s % 10 > 0) { // make start point's end digit to 0, but not 0
calc(s);
++s;
} else if (n % 10 != 9) { // make end point's end digit to 9
calc(n);
--n;
} else { // solve subproblem
int repeatTime = (n / 10 - s / 10 + 1);
for (int i = 0; i < DECIMAL; ++i) {
result[i] += repeatTime * d;
}
s /= 10, n /= 10, d *= 10; // discard the end digit
}
}
calc(n); // last number
for (int i = 0; i < DECIMAL; ++i) {
printf("%d ", result[i]);
}
return 0;
}
calc: 입력된 숫자의 각 자릿수가 몇 번 등장하는지를 계산d: 현재 계산 중인 자릿수를 기록result[]: 각 자릿수가 몇 번 등장하였는지를 기록