📘 BOJ 1019 – 책 페이지

문제 링크: https://www.acmicpc.net/problem/1019
유형 : 수학, 구현
난이도 : 플레티넘 5

---

📍 문제 요약

1부터 N까지 모든 수를 쓸 때, 각 숫자(0~9)가 몇 번 등장하는지를 구하는 문제입니다.
예를 들어 N=13이면 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

→

• 1은 6번,
• 0은 1번,
• 2~3은 각각 2번,
• 나머지는 1번씩 등장합니다.

---

⚙️ 접근 과정

1️⃣ 단순 구현의 한계

가장 먼저 떠올릴 수 있는 방법은
for i in range(1, N+1) 반복문을 돌면서 각 자릿수를 세는 방식입니다.

하지만 N이 최대 $10^9$까지 가능하기 때문에
O(N log N) 은 시간 초과가 납니다.

---

2️⃣ 자릿수별 패턴 관찰

자릿수 단위로 보면, 반복되는 규칙이 있습니다.

자릿수	구간 예시	각 숫자의 등장 횟수
1의 자리	0~9	0~9 각각 1번씩
10의 자리	00~99	0~9 각각 10번씩
100의 자리	000~999	0~9 각각 100번씩

즉, 한 자릿수 단위로 보면 “0~9가 동일한 빈도로 반복”된다는 특징이 있습니다.
이 구조를 이용하면 한 번에 여러 개의 숫자를 묶어서 계산할 수 있습니다.

그렇다면 10의 자릿수부터는 어떻게 될까요?
10 ~ 19 까지 10의 자릿수만 본다면 1이 총 10개 등장합니다.
100 ~ 199 까지 100의 자릿수만 본다면 1이 총 100개 등장합니다.

즉, 각 자릿수만큼 0~9가 등장하게 됩니다.

---

3️⃣ 구간을 블록 단위로 나누기

1. 현재 start = 1, end = N, digit = 1 로 시작합니다.

2. 1의 자리가 0이 될 때까지 start를 하나씩 증가시키며 개별 계산합니다.

3. 1의 자리가 9가 될 때까지 end를 하나씩 줄이며 개별 계산합니다.

4. 이제 start는 0으로 끝나고, end는 9로 끝나는 구간이 됩니다.
   → 이 구간에서는 0~9가 모두 동일한 횟수만큼 등장합니다.

5. 이때 각 숫자는 다음과 같은 횟수로 등장합니다.
   count[i] = ((end / 10) - (start / 10) + 1)

6. 이후 start /= 10, end /= 10, digit *= 10 으로 다음 자리로 이동합니다.

---

4️⃣ 점화식 도출

위의 과정을 수식으로 정리하면 다음과 같습니다.

각 자릿수별 등장 횟수

• digit 자리에서, 0~9는 동일하게 등장함 → count[i] += block * digit
• block의 개수는 (end/10 - start/10 + 1)
• 단, start, end가 완전한 0~9 형태가 되지 않았다면 앞뒤에서 개별 계산을 보정해야 함

이 로직은 결국 다음 점화식으로 귀결됩니다.

즉, 각 자릿수의 기여도를 digit 단위로 한 번에 더하고
다음 자리로 넘겨가며 반복하는 구조입니다.

---

💻 코드

import java.io.*;
import java.util.*;

public class Main {

	static int[] cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int end = Integer.parseInt(br.readLine());

		cnt = new int[10];

		int start = 1; // 1 ~ end까지 모든 수 구해야함
		int digit = 1; // 자릿수

		while (start <= end) {

			// 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가
			while (start < 10 && start <= end) {
				cnt[start++] += digit;
			}

			// 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소
			while (end % 10 != 9 && start <= end) {
				count(end--, digit);
			}
			
			if(start > end) break;

			for (int i = 0; i < 10; i++) {
				cnt[i] += ((end / 10) - (start / 10) + 1) * digit;
			}

			end /= 10;
			start /= 10;
			digit*=10;
		}
		
		for(int i = 0; i<10; i++) {
			System.out.print(cnt[i] + " ");
		}
	}

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

---

🧩 단계별 실행 예시 (N = 321)

1️⃣ 초기값
start = 1, end = 321, digit = 1

2️⃣ 앞쪽 정렬
start를 10이 될 때까지 개별 카운트 → 1~9 카운트 완료

3️⃣ 뒤쪽 정렬
end % 10 != 9 → end = 319까지 내려가며 count(321, 320) 수행

4️⃣ 본 블록 처리
start = 10, end = 319,
→ ((end/10)-(start/10)+1)*digit = (31 - 1 + 1) * 1 = 31
→ 각 숫자에 31번씩 더해짐

5️⃣ 다음 자리로 이동
start /= 10 = 1, end /= 10 = 31, digit *= 10 = 10

이 과정을 자릿수별로 반복하면서 모든 자릿수를 완성합니다.

---

🧮 복잡도 분석

항목	설명
시간 복잡도	O($log N$)
공간 복잡도	O(1) (고정된 배열 10개)
핵심 연산	while 루프에서 자릿수마다 일정 횟수의 반복만 수행

---

✅ 정리

단계	설명
1	start, end 정렬 (1의 자리 0과 9 맞추기)
2	정렬된 구간은 0~9가 동일한 빈도로 반복됨
3	한 번에 ((end/10)-(start/10)+1)*digit 만큼 더하기
4	자릿수를 올려 digit *= 10, 반복
5	모든 자릿수를 합산하면 각 숫자의 총 등장 횟수 완성

---

💡 마무리

이 문제의 핵심은 규칙적인 자릿수 패턴을 이용해 구간을 묶는 것입니다.
각 자리에서 숫자들이 반복되는 횟수를 수학적으로 계산하면
1~N까지를 직접 세지 않고도 정확히 구할 수 있습니다.

---

📄 요약

• 완전 탐색 불가능 → 자릿수별 규칙 관찰
• 블록 정렬 후 한 번에 더하기
• 점화식으로 반복 계산
• 시간복잡도 O(logN)

---