BOJ 11170 - 0의 개수

문제

N 이상 M 이하의 정수를 모두 쓸 때, 숫자 0이 총 몇 번 등장하는지 구하라.

입력

테스트 케이스 수 T, 각 케이스마다 N, M이 주어진다.

출력

각 케이스마다 0의 등장 횟수를 출력한다.

예제

입력	출력
`3` `0 9` `10 19` `100 199`	`1` `1` `20`

풀이

자릿수별로 0의 등장 횟수를 수학적으로 계산하여 O(log M)에 해결한다.

solve(v) 함수는 0부터 v까지 0의 등장 횟수를 계산한다
각 자릿수 위치(1, 10, 100...)에서 해당 자리가 0인 수의 개수를 누적한다
해당 자리가 0이면 v % pv + 1을 더하고, 0보다 크면 pv를 더한다
solve(M) - solve(N-1)로 구간의 0 개수를 구한다

핵심 아이디어: 누적합 방식(solve(M) - solve(N-1))으로 구간 문제를 변환하고, 각 자릿수 위치별로 0이 등장하는 수의 패턴을 수식으로 계산한다.

코드

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int solve(int v)
{
  if (v < 0)
    return 0;
  if (v == 0)
    return 1;
  int ans = 1;
  int pv = 1;
  for (int pos = 0;; pos++)
  {
    if (v / pv / 10 == 0)
      break;
    ans += (v / pv / 10 - 1) * pv;
    if (v / pv % 10 == 0)
      ans += (v % pv) + 1;
    else
      ans += pv;
    pv *= 10;
  }
  return ans;
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T-- > 0)
  {
    int n, m;
    cin >> n >> m;
    cout << solve(m) - solve(n - 1) << "\n";
  }
  return 0;
}

복잡도

시간: O(T * log M) (자릿수만큼 반복)
공간: O(1)

문제