bj1019 책 페이지

문제

• 백준 URL: 책 페이지
• 난이도 플래티넘 5

풀이

n=int(input())
ans=[0]*10
add=0
i=1
while n!=0:
    c=n%10
    n//=10
    ans[0]-=i
    for j in range(c):ans[j] += (n+1)*i
    ans[c] += n*i+1+add
    for j in range(c+1,10):ans[j] += n*i
    add+=c*i
    i*=10
print(" ".join(map(str,ans)))

해당 코드는 숫자를 가장 낮은 자릿수(일의 자리)부터 하나씩 처리하며 올라간다. 각 자릿수를 처리할 때마다 해당 자릿수에 0부터 9까지의 숫자가 몇 번 나타나는지를 계산하여 ans 배열에 누적한다.
i는 현재 자릿수, c는 현재 자릿수의 숫자이다. 그리고 다음 자릿수를 처리하기 위해 n을 업데이트한다.

    ans[0]-=i

1~N까지 세는 과정에서 불필요하게 포함된 맨 앞자리 0들을 빼준다.

    for j in range(c):
	    ans[j] += (n+1)*i

현재 자릿수(c)보다 작은 숫자(0 ~ c-1)의 개수를 계산한다.

• 예: N=123, 현재 일의 자리(c=3) 처리 중. n=12, i=1
• 0, 1, 2는 0~129 범위에서 일의 자리에 각각 (12+1)=13번씩 나타난다.

    ans[c] += n*i+1+add

현재 자릿수(c)와 같은 숫자의 개수 계산

• 예: N=123, 현재 일의 자리(c=3) 처리 중. n=12, i=1, add=0
• 0~119 범위에서 일의 자리에 3은 12번 나타나고 (n*i)
• 120~123 범위에서는 123의 3이 한 번(+1), 그 이전 자릿수 값(add)만큼 더 나타난다.

    for j in range(c+1,10):
	    ans[j] += n*i

현재 자릿수(c)보다 큰 숫자(c+1 ~ 9)의 개수 계산

• 예: N=123, 현재 일의 자리(c=3) 처리 중. n=12, i=1
• 4~9는 0~119 범위에서 일의 자리에 각각 12번씩 나타난다.