[백준 1019] 책 페이지 (C#, C++) - soo:bak

문제 링크

1019번 - 책 페이지

설명

1부터 주어진 페이지까지 모든 페이지 번호에서 0부터 9까지 각 숫자가 몇 번씩 쓰이는지 세는 문제입니다.

접근법

모든 페이지를 하나씩 확인하면 시간이 오래 걸리므로, 구간을 압축하여 한 번에 계산하는 방식을 사용합니다.

먼저 시작 위치의 끝자리가 0이 될 때까지 한 장씩 세고, 끝 위치의 끝자리가 9가 될 때까지도 한 장씩 셉니다. 이렇게 양 끝을 정리하면 가운데에는 연속된 10개씩의 묶음만 남게 됩니다.

이 묶음 안에서는 끝자리에 0부터 9까지 모든 숫자가 동일한 횟수만큼 등장하므로, 묶음의 개수만큼 각 숫자의 등장 횟수에 더해줍니다. 그런 다음 끝자리를 떼어내고 한 자릿수 위로 올라가 같은 과정을 반복합니다.

---

Code

C#

using System;

class Program {
  static long[] cnt = new long[10];

  static void AddDigits(int num, long mult) {
    while (num > 0) {
      cnt[num % 10] += mult;
      num /= 10;
    }
  }

  static void Count(int l, int r, long mult) {
    while (l % 10 != 0 && l <= r) {
      AddDigits(l, mult);
      l++;
    }
    if (l > r) return;
    while (r % 10 != 9 && l <= r) {
      AddDigits(r, mult);
      r--;
    }
    var block = r / 10 - l / 10 + 1;
    for (var i = 0; i < 10; i++) cnt[i] += block * mult;
    Count(l / 10, r / 10, mult * 10);
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    Count(1, n, 1);
    Console.WriteLine(string.Join(" ", cnt));
  }
}

C++

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

typedef long long ll;

ll cnt[10];

void addDigits(int x, ll mul) {
  while (x) {
    cnt[x % 10] += mul;
    x /= 10;
  }
}

void count(int l, int r, ll mul) {
  while (l % 10 != 0 && l <= r) {
    addDigits(l, mul);
    ++l;
  }
  if (l > r) return;
  while (r % 10 != 9 && l <= r) {
    addDigits(r, mul);
    --r;
  }
  ll block = r / 10 - l / 10 + 1;
  for (int i = 0; i < 10; i++) cnt[i] += block * mul;
  count(l / 10, r / 10, mul * 10);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  count(1, n, 1);
  for (int i = 0; i < 10; i++) cout << cnt[i] << (i == 9 ? '\n' : ' ');

  return 0;
}