[Python 3] BOJ - 1019 "책 페이지"

 # 문제 링크 : https://www.acmicpc.net/problem/1019

1019번: 책 페이지

 # 풀이 :

규칙을 찾지 못해 꽤나 오랜시간 걸린 문제이다. 개인적으로 문제의 핵심은 규칙성 이해이다. 

 

<그림 1. N = 20, M = 29인 경우>

 위의 그림 1은 20이상 29이하의 모든 수 중 일의 자리수를 나타낸 것이다. 이때 모든 일의 자리수 (1 ~ 9)는 1번씩 반복된다. 따라서 '?'에 들어갈 숫자는 1이다. 여기서 1은 자세히 보면 20의 십의 자리인 2와 29의 십의 자리인 2를 빼고 1을 더한 수이다. 따라서 두자리 수 일 때 범위에 속하는 일의 자리수를 구하는 규칙성은 알게 되었다. 그렇다면 세자리 수 일때도 이러한 규칙성이 성립하는가?

 

<그림 2. N = 200, M = 299인 경우>

 그림 2에서 각 자리수의 일의 자리는 파란색으로 나타내었다. 빨간색으로 나타낸 십의 자리수는 그림1에서의 일의 자리수라고 할 수 있다. 즉, 원래 20이었는데 단순히 뒤에 3이 붙었다면 결과적으로 203인 수가 만들어 지는 경우라 할 수 있다. 여기서 '?', 즉 일의 자리 수가 각각 몇번 반복되는가? 물론 일일이 셀 수도 있지만 답은 10이다. 과연 그림1에서의 규칙성이 적용되는가? 그렇다. 왜냐하면 29 - 20 + 1 = 10이기 때문이다. 그렇다면 십의 자리수도 일의 자리 수의 규칙과 같은가? 그렇지 않다. 왜냐하면 2 - 2 + 1 = 1이기 때문이다. 실제로 그림 2에서 빨간색 십의 자리 숫자들은 1부터 9까지 각각 10번 나타나게 된다. 따라서 일의 자리를 구할 때의 규칙성이 이어지지 않는다는 것이다. 그러나, (2 - 2 + 1) * 10이면 십의 자리에 있어서도 규칙성을 적용할 수 있다.

 만일 N = 2000이고 M = 2999 였다면 백의 자리는 사실 그림 2에서의 예시에 10배씩 증가한 것이다. 따라서 세 자리 숫자가 자릿수를 한칸 늘려야 하므로 각각 10개의 가지를 치게 된다. 따라서 그림2에서 0부터 9까지의 십의 자리 숫자, 즉 빨간색 숫자들은 각각 10번씩 반복되기 때문에 이 경우 일의 자리 숫자는 각각 (299 - 200 + 1) * 1 = 100번, 십의 자리 숫자는 각각 (29 - 20 + 1) * 10 = 100번, 백의 자리 숫자는 (2 - 2 + 1) * 100 = 100번 반복된다.

 

 따라서 a가 b보다 크고 두 수 모두 10^k 이상인 자릿수를 가질 때 일반화된 수식은 아래와 같다.

우선 이 식을 적용하기 전, 이 규칙성은 항상 a가 9로 끝나고 b가 0으로 끝나야 한다는 점이다. 따라서 조건을 맞춰 주기 위해 만일 a가 9로 끝나지 않는다면 계속 감소시켜주되, 그 때 그 수를 이루는 각 숫자의 갯수도 같이 세어주고 b 역시 계속 증가시키면서 각 숫자의 갯수도 같이 세어 주면 된다.

 

 따라서 반복의 흐름은 

1. a가 9로 끝나는가

1- 1. 그렇지 않다면 각 자릿수를 세준다 + a를 1씩 빼준다

2. b가 0으로 끝나는가

2- 1. 그렇지 않다면 각 자릿수를 세준다 + b를 1씩 더해준다

3. a,b 모두 10으로 나눠준다

4. 위 식을 계산한다

5. 다시 1로 돌아가 반복

 

 # 코드

import sys

# ans = 1부터 9까지 각가 몇번 등장했는지 세주는 배열
ans = [0] * 10

# 입력
end = int(sys.stdin.readline())

# 위 글에서 k의 역할을 하는 point
point = 1
# 문제의 조건에 따라 1부터 시작
start = 1

# calc : a,b가 9또는 0으로 끝나지 않을 때 각 자리수를 ans에 카운트 시키는 함수
def cal(x,ans,point):
    while x > 0:
        ans[x % 10] += point
        x //= 10
        

while start <= end:
    while end % 10 != 9:
        cal(end, ans, point)
        end -= 1
    if end < start:
        break
    while start % 10 != 0:
        cal(start, ans, point)
        start += 1
    start //= 10
    end //= 10
    for i in range(10):
        ans[i] += (end - start + 1) * point
    point *= 10

# 출력부
for i in range(10):
    print(ans[i], end= ' ')