[백준 1019번] 책 페이지 (Python3)

import sys
input = sys.stdin.readline

def page(N,n):
  c = len(str(N))-1
  a = int(str(N)[0])
  if c == 0:
    if n > a:
      return 0
    else:
      return 1
  result = a*c*10**(c-1) + page(N-a*10**c,n)
  if n > a:
    return result
  if n == a:
    return result + (N-a*10**c+1)
  if n == 0:
    return result + (c-len(str(N-a*10**c)))*(N-a*10**c+1) + 10**c
  return result + 10**c

def zeropage(N):
  c = len(str(N))-1
  result = 0
  for i in range(c+1):
    result += 10**i
  return result

N = int(input())

print(page(N,0)-zeropage(N), end=" ")
for n in range(1,10):
  print(page(N,n),end=" ")

 

쉬운 문제라고 생각했는데 생각보다 까다로운 문제였다.

1~9의 일반항을 구하는건 떠올리기 굉장히 쉽다.

 

간단하게만 요약하면

1. N의 차수와 맨 앞자리 숫자를 c,a로 둔다.

2. 10에서는 1~9의 숫자가 각각 1번씩, 100에서는 20번, 1000에서는 300번 나오는 규칙을 이용해서 10의 c승일 때 일반항을 c*10^(c-1)로 세운다.

(이유: 1000을 예로 들면 n은 1의 자리에서 100번, 10의 자리에서 100번 100의 자리에서 100번 등장한다)

3. 따라서 앞자리가 a면 a*10^c 까지 등장하는 n의 개수는 a*c*10^(c-1) 이다.

4. 이제 앞자리 a를 떼어버렸다고 생각하고 나머지 숫자에서의 값은 재귀함수로 불러온다.

 

여기까지는 쉬운데 문제는 0이었다. 0의 문제점은 맨 앞자리에 올 수 없다는 것이었다. 따라서 맨 앞자리에 0이 있다고 가정하고 문제를 풀고, zeropage 함수를 통해서 맨 앞자리 0의 개수만큼을 빼서 출력해주었다.

또, 1000013 같은 수를 예로 들면, 맨 앞 1을 떼어버리면 13이 되는데, 이렇게 되면 1과 13 사이의 0000을 세지 못하게 된다. 그래서 이에 대한 예외 if문도 넣어주었다.

 

 

오늘의 교훈) 0의 성질에 대해서 고민해보자