Tip - N까지의 각 숫자가 출현하는 개수를 세는 방법

$L \le N \le R,~ L,N,R \in \natnums$ 를 만족하는 $N$ 의 집합에서 $D(0 \le D \le 9)$라는 숫자는 몇번 등장할까?

우리가 $f(N,K,D)=[1, N]$ 까지에 존재하는 자연수 중 $D(0 \le D \le 9)$ 가 $10^k$ 자리에 등장하는 횟수라고 하자.

그럼$L \le N \le R$ 의 $N$ 에서 $D$가 등장하는 횟수는 $\displaystyle\sum_{K=0}^\infty (f(R,K,D)-f(L-1,K,D))$ 이다.

$\infty$ 라고 표현했지만 문제에서 주어지는 수는 대부분 20자리 이내이므로 시간적으로 구하기에 충분하다.

그럼 $f$ 함수만 적절히 잘 구현한다면 이러한 문제를 해결할 수 있다는 결론이 나온다.

$f$ 함수 작성법을 익히면 BOJ 1019 - 책 페이지 나 BOJ 1081 - 합 같은 문제를 날로 먹을 수 있다.

원래 이런 문제들은 제일 뒷자리를 $0,~9$로 맞춰주고 $1$의자리 수에서 $0 \sim 9$ 가 반복되는 개수는 $10$의 자리 수들간의 차이, $10$의 자리 수에서 $0 \sim 9$ 가 반복되는 개수는 $100$의 자리 수들간의 차이 * $10$ 이런식으로 계산해주는 문제인데, $f$ 함수를 새롭게 정의함으로 훨씬 풀기 쉬운 문제가 된다. 백준님이 작성하신 풀이

$f(N,K,D)$ 함수 작성Permalink

int f(int N, int K, int D) {  
     
}

여기서부터 시작해보자.

일단 $D=0$ 인 경우는 좀 다르게 고려해야해서 제외하고 다루자.

예시를 들어서 설명함이 더 쉬우므로, $N=12345,~K=2,~D=3$ 라고 해보자.

백의자리에 3이라는 숫자가 몇번 나오는지 알고 싶다는 뜻

$300$ 보다 큰 자리수인 $12000$ 만 두고 생각해보자.

$12000$ 까지 갈 때 백의자리에 $3$이 나오는 횟수는 몇번일까?

00300 ~ 00399 => 100
01300 ~ 01399 => 100
...
11300 ~ 11399 => 100

총 12번임을 알 수 있다.

그러면 일단 $12 \cdot 100$ 이 곱해져야 합이 알 수 있다.

일단 이 함수에서 $10^K$ 를 다루어야 할 일이 많으므로, 10의 거듭제곱수들을 전처리해두자.

int f(int N, int K, int D) {  
   // 아직 전처리가 되어있지 않을 때만 계산
   if (ten[0] == 0) {  
      ten[0] = 1;  
      for (int i = 1; i < 10; i++) ten[i] = ten[i - 1] * 10;  
   }  
}

여기서 12는 $\left\lfloor \dfrac N{10^{K+1}} \right\rfloor$ 임을 알 수 있다.

int q = N / ten[K+1];

그럼 여기에 $1200$은 $10^K$를 곱해준 값이므로 다음과 같이 구할 수 있다.

int f(int N, int K, int D) {  
   int ans = 0;  
   ...
   int q = N / ten[K+1];  
   ans += q * ten[K]; // here
  
   return ans;  
}

$N=12345$ 에서 $12000$ 부분이 아닌 $345$ 부분을 살펴보자.

이제 $123??$ 와 같은 개수가 몇번이 나오는지만 세주면 된다.

지금은 백의 자리수($10^K$) 가 $3$ 이여서 우리가 구하려는 $D=3$ 과 일치하는 특수한 경우인데, 원래는 세 가지로 나눌 수 있다.

1. $10^K$ 자리수가 $D$ 보다 작은 경우

이 경우 더 더해져야 할 수는 0이다.

2. $10^K$ 자리수가 $D$ 보다 큰 경우

이 경우 $123??$ 가 $12300 \sim 12399$ 로 또 $10^K$ 개 존재할 것이므로 정답에 $10^K$를 더해주면 된다.

3. $10^K$ 자리수가 $D$ 와 같은 경우

$123??$ 에서 $12300 \sim 12345$ 개수를 세주면 된다. 이 땐, $12345$를 $10^K$ 로 나머지 연산을 한 값 $45$ 에 $1$을 더해주면 된다.

이를 코드로 표현하면 다음과 같다.

우선 $10^K$ 자리 수가 뭐인지를 알아낸다.

$\left\lfloor \dfrac N{10^K} \right\rfloor$ 의 1의 자리 수가 결국 그것이기 때문에 다음과 같이 구한다.

int k_digit = N / ten[K] % 10;

이제 위 세 경우를 대입해서 다음과 같다.

int f(int N, int K, int D) {  
   int ans = 0;  
   ...
  
   int k_digit = N / ten[K] % 10;  
   if (k_digit > D) ans += ten[K];  
   else if (k_digit == D) ans += N % ten[K] + 1;  
  
   return ans;  
}

이제 BOJ 1081 - 합 는 0을 고려할 필요가 없는 경우이므로 풀 수 있다. 오버플로우에 유의해서 풀어보도록 하자.

void solve() {  
   int L, U;  
   cin >> L >> U;  
  
   auto ff = [&](int X) {  
      int ret = 0;  
      for (int d = 1; d <= 9; d++) {  
         for (int k = 0; k < 15; k++) {  
            ret += f(X, k, d) * d;  
         }  
      }  
      return ret;  
   };  
  
   cout << ff(U) - ff(max(0ll, L - 1));  
}

$D=0$ 인 경우Permalink

$D=0$ 인 경우가 특별한 이유는 Leading Zero 때문이고 두 가지를 처리해야 한다.

1. $10^K$ 보다 크거나 같은 수의 Leading Zero 처리

$N=100$ 인데 $10^3$ 자리수에 $0$이 몇개가 나오냐라고 물어본다면 $0$개여야 하는데 $10^3$ 자리수가 $D$와 같은 경우에 걸리기 때문에 잘못된 답이 계산될 수 있다.

실제로 $101$이 나옴을 확인할 수 있다. 왜 그렇게 나오는지 생각해보도록 하자.

따라서 다음과 같이 처리해준다.

int f(int N, int K, int D) {  
   int ans = 0;  
   ...
  
   int q = N / ten[K + 1];  
   if (D == 0 && q == 0) return 0;  
   ... 
  
   return ans;  
}

2. $10^K$ 보다 작은 수의 Leading Zero 처리

$N=12345$ 에서 백의 자리의 $0$ 를 센다고 하자.

$00000 \sim 00099$ 까지의 숫자는 세주면 안된다. 이 또한 Leading Zero이기 때문이다.

따라서 $10^K$ 를 한 번 빼주면 끝이다.

완성된 우리의 $f$ 함수는 다음과 같다.

int ten[20];  
  
int f(int N, int K, int D) {  
   int ans = 0;  
   // 아직 전처리가 되어있지 않을 때만 계산  
   if (ten[0] == 0) {  
      ten[0] = 1;  
      for (int i = 1; i < 20; i++) ten[i] = ten[i - 1] * 10;  
   }  
  
   int q = N / ten[K + 1];  
   if (D == 0 && q == 0) return 0;  
   ans += q * ten[K];  
  
   int k_digit = N / ten[K] % 10;  
   if (k_digit > D) ans += ten[K];  
   else if (k_digit == D) ans += N % ten[K] + 1;  
  
   if (D == 0) ans -= ten[K];  
  
   return ans;  
}

이제 BOJ 1019 - 책 페이지 문제도 풀어보도록 하자.

이진수에의 적용Permalink

BOJ 9527 - 1의 개수 세기

지금까지는 $10$진수에 대해서만 다루었지만, 이제 어떤 수 $N$을 이진수로 나타냈을 때 $2^K$ 자리에 $1$ 이 나오는 개수를 세고 싶다고 하자.

물론 2진수에서도 $0$을 셀 수 있지만 이 설명에선 그 내용은 빠진다. 물론 그것도 똑같이 구현하면 된다.

똑같다. $f(N,K)$ 를 작성해주면 된다.

$D=1$ 이므로 생략한다.

$N=10110_2$ 에서 $1(=00001_2)$ 부터 시작해서 $N$ 까지 $2^2$ 자리에 $1$ 이 몇개가 나오는지 알고싶다고 하자.

00100 ~ 00111 (2^2 개)
01100 ~ 01111 (2^2 개)

이제 큰쪽은 다 셌다.

아까 세 가지 경우를 나눴는데, 이제 $2^K$ 자리수가 $1$ 보다 커질일은 없으므로 그 경우를 제외하고 $2^K$ 자리수가 $1$ 인경우만 세주면 된다.

완성된 함수는 다음과 같고,

int two[64];  
  
int f(int N, int K) {  
   int ans = 0;  
   // 아직 전처리가 되어있지 않을 때만 계산  
   if (two[0] == 0) {  
      two[0] = 1;  
      for (int i = 1; i < 64; i++) two[i] = (1ll << i);  
   }  
  
   int q = N / two[K + 1];  
   ans += q * two[K];  
  
   int k_digit = N / two[K] % 2;  
   if (k_digit == 1) ans += N % two[K] + 1;  
  
   return ans;  
}

2진수 비트연산으로 연산들을 좀 더 깔끔하게 처리하자면,

int f(int N, int K) {  
   int ans = 0;  
   int q = N / (1ll << (K + 1));  
   ans += q * (1ll << K);  
   if (N & (1ll << K)) ans += N % (1ll << K) + 1;  
   return ans;  
}

그냥 이렇게 써줘도 된다.