백준 1019번: 책 페이지

이 문제는 1부터 N까지 책 페이지를 넘기며 0,1,2,3,4,5,6,7,8,9 가 총 몇번 나오는지 세는 문제이다. 당연히 1부터 N까지 탐색하면 시간 복잡도가 10억이기에 시간 초과된다.

 

import sys

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

cnt=[0 for _ in range(10)]
for i in range(len(str(N))):
    a=N//(10**(i+1))
    b=(N%(10**(i+1)))//(10**(i))
    for j in range(0,10):
        if j<b:
            if j==0:
                cnt[j]+=a*(10**i)
            else:
                cnt[j]+=(a+1)*(10**i)
        if j==b:
            if j==0:
                cnt[j]+=(a-1)*(10**i)+(N%(10**i)+1)
            else:
                cnt[j]+=a*(10**i)+(N%(10**i)+1)
        if j>b:
            cnt[j]+=a*(10**i)

for i in cnt:
    print(i,end=' ')

나는 먼저 1부터 N까지 진행될때 일의 자리, 십의 자리, 백의 자리.. 이렇게 자리 수 당 0123456789 가 총 몇번 나오는지 나누어 풀었다. i는 뒤에부터의 (10^i) 자리수를 표현하고 0이면 10^0, 일의자리를 탐색하는 것이다. 여기서 a는 탐색하는 자리 수 앞에 남은 숫자들이고, b는 탐색하는 자리수의 숫자이다.

 

예시로 12345를 탐색할때

 

i=0 이면 a= 1234, b= 5

i=1 이면 a= 123, b= 4

 

이렇게 반환된다. 내가 수를 이렇게 나눈 이유는 다음과 같다. N이 100일 때 십의 자리 카운트를 구하는 문제가 있다면, 먼저 최소 십의 자리가 생기는 지점은 10 부터일 것이다. 10,11,12,13,14,15,16,17,18,19 까지 총 10개의 수가 십의 자리가 1인 경우이다. 이는 1,2,3,4,5,6,7,8,9 모두 동일하게 10개씩 있을 것이다. 그렇다면 N이 200이라면, 10,11,12..19 까지 10개, 그리고 앞에 1이 붙은경우 110,111,112,113..119 이렇게 한가지가 더 생기게 된다. 만약 N이 12300 이라면 앞에 붙을 수 있는 경우가 1~122까지 총 122, 그리고 아무것도 붙지 않은 1가지 총 123가지의 경우가 10^i 만큼 생기게 된다. 여기서 앞에 붙는 수는  a로 일반화 할 수 있고, a 뒤의 숫자들을 계산하기 위해 그 자릿수의 숫자 b 도 저장해 주었다.

 

다시 N=12345로 돌아와서

먼저 12345에서 십의 자리를 (i=1) 고려할 때, 12345를 10~12299 / 12300~12345 로 범위를 나누고 첫번째 경우를 구하기 위해 a=123, b=4 로 나누어 생각한다고 하자.

만약 a가 123, (N<12300) 에서 십의자리 중 j=1,2,3을카운트 한다고 했을 때 십의 자리에서 1, 2, 3이 처음 으로 나오는 경우는 j=1일때 10부터 시작해서 10,11,12..  j=2일때 20,21,22.. j=3일때 30,31,32.. 이런 숫자일 때 십의자리 카운트가 올라가게 된다. 

 

만약 a가 10이라면 (N<100) 십의 자리 카운트는 j=1인 경우 10~19까지 10, j=2인경우 20~29까지 10, j=3인경우 30~39까지 올라가게 된다 고려해야 할 점은 j=0인경우 01,02,03,04..09 로는 카운트 하지 않는다.

 

아까 a가 123인 경우로 돌아오면, 십의 자리 카운트 할때 최소 10~12300까지라면 0을 제외한 각 자리 수는 1230 만큼 올라가게 된다. 0 은 아까 경우에서 (123-1)*10 을 한 1220만큼 올라가게 된다.

 

하지만 이는 12300까지의 카운트이고 뒤에 12300 ~ 12345까지의 카운트는 고려하지 않았다. 십의 자리를 고려한 경우 12300 ~ 12339 까지 다시 j=0, 1, 2, 3일떄는 10만큼 올라가게 된다. 4일때는 12340~12349까지 수가 완벽하게진행되지 않고 12340, 12341, 12342, 12343, 12344, 12345 이렇게 6개 (N%(10^1) = 5)+1 만큼 올라가게 된다. 

 

그렇게 N=12345, i=1, a=123, b=4 인 경우, 숫자 카운트는

 

j=0은 (123-1)*10 + 10,

j=1~3까지는 (123)*10 + 10,

j=4인 경우 123*10 + 5,

j=5~9 인경우 123*10

 

으로 카운트가 존재하게 된다. 이제 일반화를 해보자. 아래가 위 과정이 코드로 일반화를 시킨 경우다.

 

j=0은 (123-1)*10 + 10               ->           j<b이고 j==0 상태 (a-1)*(10^i)+(10^i) = a*(10^i)

j=1~3까지는 (123)*10 + 10       ->           j<b, j != 0 상태  a*(10^i) +(10^i) = (a+1)*(10^i)

j=4인 경우 123*10 + 5              ->           j==b, j != 0 상태 a*(10^i) + (N%(10^i))

j=5~9 인경우 123*10                ->           j>b, 상태  a*(10^i)

 

이렇게 i를 일의자리부터 N의 십진수 최대 자리까지 탐색을 해 주며 누적하여 더하면 총 답이 나오게 된다. 뭔가 수학 사고력 문제를 푸는 것 같아 힘들었던 문제였다.