책 페이지
이번에 풀어볼 문제는 책 페이지입니다.
\(1\)페이지부터 \(N(\le 1,000,000,000)\)페이지까지, 0부터 9까지의 숫자가 몇 개 나오는지 찾아내면 되는 간단한 문제입니다.
간단하다고 했지만, 실제로는 절대 그렇지 않죠. \(1\)부터 진짜로 \(N\)까지 숫자를 일일이 다 세고 있으면 시간초과 납니다. 대체로 이 문제를 검색해서 나오는 문제풀이 글을 보면 백준님의 강의 자료를 바탕으로 쓴 것들이 많습니다. 첫 자리를 \(0, 9\)로 맞춰서 개수를 찾는 그 풀이 말입니다.
하지만 저는 좀 다르게 풀어봤습니다. \(A\)부터 \(B\)까지 찾을 것도 없이 그냥 \(1\)부터 훑으면 되니까요. 그럼 제가 이 문제에 어떻게 접근했는지 함께 봅시다.
어떤 수 \(N\)이 \(n\)자리의 일련의 연속되는 숫자들로 이루어져있다고 합시다. 그렇다면 \(N = a_0 a_1 … a_i … a_{n-1}\)으로 쓸 수 있습니다. 여기서 붙여 쓴 건 곱한다는 의미가 아닙니다. \(12345…\)처럼 한 자리의 숫자들이라고 보면 됩니다.
이 숫자를 \(i\)번째 자리를 기준으로 세 덩이로 나눌 수 있습니다. 예를 들어 12345를 세 번째 자리를 기준으로 나누면 12, 3, 45가 되는 것처럼요. 앞의 덩어리를 \(sup\), 뒤의 덩어리를 \(sub\)라 하겠습니다. 그리고 기준이 된 자리의 수는 \(digit = a_i\)이라 하면,
\[N = 10^{i} sup + 10^{i - 1}a_i + sub\]이 됩니다… 이게 뭔 식이냐 싶으시면 예를 들어
\[12345 = 10^{i} 12 + 10^{i - 1}3 + 45 = 12000 + 300 + 45\]이렇게 된다고 보시면 됩니다. 그냥 \(0\)을 몇 개나 붙여야 하나를 수학적으로 쓴 거죠.
이제 \(i\)번째 자리에 \(3\)이 몇 번이나 들어갈지 생각해봅시다.
그러기 위해서는 일단 \(a_i = 3\)으로 고정시켜놓고 다른 숫자들을 이리저리 바꿔보면 될 것 같습니다.
\(sup\)이 \(12\)이라면, \(12300\)부터 \(12345\)까지 중에서 세 번째 자리에 3이 들어가는 걸 다 찾으면 됩니다. 0부터 45까지, \(sub + 1\)개네요.
\(sup\)이 최대값보다 작다면 식은 약간 달라집니다. 예를 들어 \(sup = 11\)이라면, 조합 가능한 숫자는 \(11300\)부터 \(11399\)까지입니다. 이 때의 개수는 \(10^{i - 1}\)입니다. 수식이 헷갈리신다면, 예로 든 이 숫자는 100입니다. 그냥 \(sub\)보다 큰 가장 작은 10의 거듭제곱이라고 보시면 됩니다.
\(i\)번째 자리에 \(3\)보다 작은 수는 몇 번 들어갈까요? 예를 들어 \(2\)가 들어간다면, \(sup\)의 값에 상관없이 \(\times\times200\)부터 \(\times\times299\)까지 찾을 수 있습니다. 이 때 조합 가능한 수는 그냥 최대값인 \(10^{i - 1}\)이 되겠네요.
그렇다면 \(i\)번째 자리에 \(4\)는 몇 번이나 들어갈까요? 일단 \(sup\)이 최대값이 아니라면, \(\times\times400\)부터 \(\times\times499\)까지 100개씩은 찾을 수 있습니다. 하지만 \(sup\)이 최대값이라면 말이 달라집니다. \(12400\)부터는 조합이 불가능하므로 개수는 그냥 0입니다.
이제 여기서 식을 하나 도출하게 됩니다. \(i\)번째 자리에 1부터 9까지의 수 중 하나인 \(digit\)이 들어가는 경우의 수 \(n(digit_i)\)는
\[n(digit_i)=10^{i - 1}sup + \begin{cases} 10^{i - 1}, & \mbox{if }digit \lt a_i \\ sub + 1, & \mbox{if }digit = a_i \\ 0, & \mbox{if } digit \gt a_i \end{cases}\]k = pow(10, i - 1);
ll digit_i = sup * k + (d < a_i ? k : d == a_i ? sub + 1 : 0);입니다. 이게 어떻게 성립하냐면, \(0\)부터 \(sup - 1\)까지는 \(digit\)과 \(a_i\)의 대소관계에 상관없이 무조건 \(10^{i - 1}\)개를 찾을 수 있으니 일단 \(10^{i - 1}sup\)를 더해준 후, \(sup\)이 최대값일 때만 따로 예외처리를 한 겁니다.
위 식을 토대로 한 번 값을 구해봅시다. 12345의 3번째 자리에 2가 들어가는 개수는
\[100 \times 12 + 100 = 1300\]3이 들어가는 개수는
\[100 \times 12 + 45 + 1 = 1246\]4가 들어가는 개수는
\[100 \times 12 + 0 = 1200\]이렇게 됩니다. 그럼 이제 1부터 9까지 중 하나의 숫자인 \(digit\)이 숫자 N에 나타나는 개수 \(n(digit)\)은 다음 식으로 구할 수 있게 됩니다.
\[n(digit) = \sum_{i = 1}^{\lfloor log_{10}N \rfloor}{n(digit_i)}\]만일 \(digit\)이 0이라면 식은 조금 달라집니다.
\(i\)번째 자리에 0이 들어간다면, \(sup\)은 0이 될 수 없습니다. 그러니 \(1\)부터 \(sup - 1\)까지는 \(10^{i-1}\)개를 찾아줍니다. 그리고 \(sup\)이 최대값일 때의 예외처리를 해주면 됩니다.
\[n(0_i)=10^{i - 1}(sup - 1) + \begin{cases} 10^{i - 1}, & \mbox{if }a_i \ne 0 \\ sub + 1, & \mbox{if }a_i = 0 \end{cases}\]k = pow(10, i - 1);
ll _0_i = (sup - 1) * k + (a_i ? k : sub + 1);이제 준비는 모두 끝났습니다. 남은 건 함수를 완성하는 일이죠.
\(10^i\)값을 빠르게 구하기 위해 for문 안에 별도의 변수 k를 넣고 10씩 곱해주겠습니다.
#include <iostream>
#include <cmath>
typedef long long int ll;
/// <summary>
/// N (<= 1,000,000,000)에 한 자리 숫자 d가 몇 번 나오는지 구하는 함수
/// </summary>
/// <param name="d">digit, 0부터 9까지 들어갈 수 있습니다.</param>
/// <param name="n">N, 문제에서 주어진 수</param>
/// <returns>d가 나오는 개수를 반환합니다.</returns>
ll F(int d, ll n) {
ll result = 0;
// 1의 자리부터 N의 끝자리까지 값을 다 더합니다.
for (ll i = 0, k = 1; i <= log10(n); ++i, k *= 10) {
ll sup = n / k, sub = n % k, a_i = sup % 10; sup /= 10;
// 만약 d가 0이 아니라면 n(digit_i)의 값을 누적합니다.
if (d) result += sup * k + (d < a_i ? k : d == a_i ? sub + 1 : 0);
// 만약 d가 0이고 sup이 0이 아니라면 n(0_i)의 값을 누적합니다.
else if (sup) result += (sup - 1) * k + (a_i ? k : sub + 1);
}
return result;
}\(1\)부터 \(N\)까지 숫자의 개수를 다 찾는다면, \(N\)개의 수를 각각 10씩 나눠가며 비교를 하므로 \(O(N\log N)\)만큼의 시간이 소모됩니다. 하지만 위의 방식으로 값을 찾게 되면 그냥 \(N\)만 한 번 훑으므로 \(O(\log N)\)이면 됩니다.