[python] 백준 1019 : 책 페이지

https://www.acmicpc.net/problem/1019

 

백준의 1019번 문제인, 책 페이지이다. 다이나믹 프로그래밍을 통해 접근하면 어렵지 않게 풀 수 있다.

 

[전체 코드]

#백준 1019: 책 페이지

n = int(input())

num = [0] * 10

start = 1

end = n

factor = 1

#start가 end보다 작거나 같을 때까지 반복

while start <= end: #start가 end보다 작거나 같을 때까지 반복

while start % 10 != 0 and start <= end: #start가 10으로 나누어 떨어지지 않고 start가 end보다 작거나 같을 때까지 반복

for i in str(start): #start 값 str으로 변환 후 대입

num[int(i)] += factor

start += 1 #이동

if start > end: #start가 end보다 크면 반복문 종료

break

while end % 10 != 9 and start <= end: #end가 9로 나누어 떨어지지 않고 start가 end보다 작거나 같을 때까지 반복

for i in str(end): #end값 변환 후 대입

num[int(i)] += factor #num에 factor값 대입

end -= 1 #이동

 

start //= 10 #start를 10으로 나눈 몫을 대입

end //= 10 #end를 10으로 나눈 몫을 대입

 

for i in range(10): #0부터 9까지 반복

num[i] += (end - start + 1) * factor

factor *= 10

#출력

for i in num:

print(i, end=' ')

 

풀이법: 다이나믹 프로그래밍

핵심 아이디어: 페이지 번호의 범위를 나눈다는 것, 자리수별로 나누어 분할로 계산하고 누적시킨다는 것 (해당 방법이 아닌 다른 방법으로 접근 시에 시간 초과가 될 수 있으니 주의하기!)