[BOJ] 1019 - 책 페이지

💻 문제: 책 페이지

문제 링크: https://www.acmicpc.net/problem/1019
알고리즘 분류: 수학(Math), 구현(Implementation)

문제 소개 🧐

전체 페이지의 수가 N인 책이 주어졌을 때, 1페이지부터 N페이지까지 모든 페이지 번호에 각각의 숫자가(0부터 9까지) 총 몇 번씩 나타나는지 계산하는 문제다. 예를 들어, 11페이지짜리 책이 있다면 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 페이지에서 각 숫자의 개수를 세어야 한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	23531	8012	6509	43.356%

입력 📝

첫째 줄에 책의 마지막 페이지 번호 N이 주어진다. (1 ≤ N ≤ 1,000,000,000)

출력 📤

0부터 9까지 각 숫자가 페이지 번호에 총 몇 번씩 등장하는지 공백으로 구분하여 출력한다.

Idea 1: 자릿수 기반 블록 단위 계산 ✨

Idea

이 문제의 핵심은 N이 매우 크기 때문에 1부터 N까지 모든 수를 순회하며 숫자를 세는 방식으로는 시간 초과가 발생한다는 점이다. 따라서 숫자의 분포에서 규칙을 찾아 계산을 최적화해야 한다.

접근 방식은 페이지 범위를 start와 end로 설정하고, 각 자릿수별로 숫자의 등장 횟수를 계산하는 것이다.

범위 설정: start는 1, end는 N으로 시작한다.
끝자리 정렬:
- end의 마지막 자리가 9가 될 때까지 end를 1씩 감소시키며, 해당 페이지 번호에 포함된 숫자들을 calc 함수로 계산한다.
- start의 마지막 자리가 0이 될 때까지 start를 1씩 증가시키며, 해당 페이지 번호들을 calc 함수로 계산한다.
블록 단위 계산: 위 과정을 거치면 start는 0으로, end는 9로 끝나게 된다. 이제 start부터 end까지 10개 단위의 블록을 한 번에 계산할 수 있다.
- start와 end를 10으로 나눈다.
- num_of_blocks = (end - start + 1) 만큼의 블록이 존재한다.
- 각 블록에서 0부터 9까지의 숫자는 place (현재 자릿수) 만큼 등장하므로, answer 배열에 num_of_blocks * place를 더해준다.
자릿수 이동: place를 10배 하여 다음 자릿수로 이동하고, start가 end보다 커질 때까지 이 과정을 반복한다.

이 방식을 사용하면, 대부분의 숫자를 개별적으로 처리하지 않고 큰 덩어리로 한 번에 계산할 수 있어 효율적이다.

Code

import sys

N = int(sys.stdin.readline().rstrip())

answer = [0 for _ in range(10)]

start = 1
place = 1  # 자릿수 

def calc(x, place):
    global answer
    while x > 0:
        answer[x % 10] += place
        x //= 10

while start <= N:
    # --- 1단계: 끝 수(N)의 끝자리를 9로 맞추는 과정 ---
    while (N % 10) != 9 and start <= N:
        calc(N, place)
        N -= 1

    if start > N:
        break

    # --- 2단계: 시작 수(start)의 끝자리를 0으로 맞추는 과정 ---
    while (start % 10) != 0 and start <= N:
        calc(start, place)
        start += 1

    if start > N:
        break

    # --- 3단계: 0과 9로 정렬된 중간 블록을 한 번에 계산하는 과정 ---
    start //= 10
    N //= 10

    # 0부터 9까지의 숫자가 몇 번 나타나는지 계산합니다.
    num_of_blocks = N - start + 1
    for i in range(10):
        answer[i] += num_of_blocks*place

    # --- 4단계: 다음 자릿수로 이동 ---
    place *= 10

print(*answer, sep=' ')

Result

결과: 성공! 🎉
자릿수를 기준으로 문제를 분할하여 규칙성을 찾아 해결하는 접근법이 유효했다.

배운 점 및 개선할 부분 🤔

규칙성 찾기: N의 범위가 큰 문제에서는 완전 탐색이 아닌, 수학적 규칙이나 패턴을 찾는 것이 문제 해결의 열쇠가 될 수 있다는 점을 다시 한번 확인했다.
구현의 디테일: start와 end의 범위를 조정하고, 각 단계에서 calc 함수를 호출하는 로직을 정확하게 구현하는 것이 중요했다. 특히 start가 N을 넘어서는 엣지 케이스를 처리하는 if start > N: break 구문이 필수적이었다.
자릿수(place)의 의미: place 변수를 이용해 각 숫자가 어느 자릿수에서 나타났는지에 따라 가중치를 부여하는 아이디어가 핵심이었다. 예를 들어, 10의 자리에서 3이 나타나는 것은 1의 자리에서 3이 10번 나타나는 것과 같다는 원리를 활용한다.

복잡해 보이는 숫자 세기 문제도 자릿수별로 나누어 생각하면 계산을 크게 단순화할 수 있다. 이 문제는 그러한 분할 정복 접근법의 좋은 예시이다.

⁂