[BOJ 1019, Python 3] 책 페이지

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

1019번: 책 페이지

 

 

풀이

n = int(input())
arr = [0] * 10
for i in range(1, n+1):
    x = str(i)
    for j in range(len(x)):
        arr[int(x[j])] += 1
print(n, '-', arr)

이 코드는 O(N^2)로 답을 구하는 경우인데, 첫번째 자리수의 값을 제외한 나머지 값들을 9로 설정하고 확인해보면 규칙성이 나옵니다.

 

9 - [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

19 - [1, 12, 2, 2, 2, 2, 2, 2, 2, 2]

29 - [2, 13, 13, 3, 3, 3, 3, 3, 3, 3]

 

위처럼 10이 더해질 때마다 모든 값에 1이 증가하는 동시에 첫 번째 자릿수의 값이 10씩 증가합니다.

 

99 - [9, 20, 20, 20, 20, 20, 20, 20, 20, 20]

199 - [29, 140, 40, 40, 40, 40, 40, 40, 40, 40]

299 - [49, 160, 160, 60, 60, 60, 60, 60, 60, 60]

 

이렇게 100이 더해질 때마다 모든 값에 20이 증가하는 동시에 첫 번째 자릿수의 값이 100씩 증가합니다.

 

999 - [189, 300, 300, 300, 300, 300, 300, 300, 300, 300]

1999 - [489, 1600, 600, 600, 600, 600, 600, 600, 600, 600]

2999 - [789, 1900, 1900, 900, 900, 900, 900, 900, 900, 900]

 

1000이 더해질 때마다 모든 값에 300이 증가하는 동시에 첫 번째 자릿수의 값이 1000씩 증가합니다.

 

 

계속 이렇게 구해보면

첫 번째 자릿수: 10 ^ (숫자의 길이 - 1)만큼 증가

모든 값: (숫자의 길이 - 1) * 10 ^ (숫자의 길이 - 2)만큼 증가하게 됩니다.

 

 

=========================================================================

 

이제 첫 번째 자릿수를 제외한 모든 자릿수의 값을 9로 바꿨을 때의 규칙성을 알아보았습니다.

이것을 이용하여 답을 구할 때는 n을 입력 받으면 첫 번째 자릿수를 제외한 모든 자릿수의 값들을 9로 바꾸어주고, n이 나올 때까지 10000, 1000, 1, 10, ... 이렇게 10^k 꼴로 나오는 값들을 빼주면 됩니다.

 

예를들어서 1557의 값을 구한다고 가정해봅시다.

1999 - [489, 1600, 600, 600, 600, 600, 600, 600, 600, 600]

1999에서 1557이 되려면 일단 백의 자리수는 400을 빼야 합니다.

100을 뺀다면 위에서 확인한 대로 두 번째 자릿수 9의 값은 8로 변하면서 100이 줄어들고, 모든 값이 20이 줄어들 것 입니다.

 

1899 - [469, 1480, 580, 580, 580, 580, 580, 580, 580, 480]

그런데 답을 확인해보면 첫 번째 자릿수인 1의 값도 100이 줄어든 것을 확인할 수 있습니다.

왜 1의 값도 줄어들은 건지 생각해보면 1999에서 1899로 가는동안 첫 번째 자릿수인 1의 출현횟수도 동시에 줄어들기 때문인 것을 알 수 있습니다.

 

1799 - [449, 1360, 560, 560, 560, 560, 560, 560, 460, 460]

1699 - [429, 1240, 540, 540, 540, 540, 540, 440, 440, 440]

1599 - [409, 1120, 520, 520, 520, 520, 420, 420, 420, 420]

 

이렇게 해서 1599까지 구했습니다. 이제 1599를 1559로 변경해주면 됩니다.

1599 - [409, 1120, 520, 520, 520, 520, 420, 420, 420, 420]

1599에서 1589로 간다면 세 번째 자릿수인 9가 8로 변하면서 10이 줄어들고, 모든 값이 1이 줄어들 것 입니다.

거기다가 첫 번째 자릿수와 두 번째 자릿수도 출현횟수가 동시에 줄어들고 있으니 1의 출현횟수와 5의 출현횟수도 10이 줄어들을 것 입니다.

1589 - [408, 1109, 519, 519, 519, 509, 419, 419, 419, 409]

1579 - [407, 1098, 518, 518, 518, 498, 418, 418, 408, 408]

 

 

1579까지 구했으므로 마지막으로 1579를 1577로 변경해주면 됩니다.

1579 - [407, 1098, 518, 518, 518, 498, 418, 418, 408, 408]

1579에서 1578로 간다면 네 번째 자릿수인 9가 8로 변하면서 1이 줄어들고, 모든 값이 0으로 줄어들 것 입니다.

거기다가 첫 번째 자릿수, 두 번째 자릿수, 세 번째 자릿수도 출현횟수가 동시에 줄어들고 있으니 1의 출현횟수는 1이 줄어들고, 5의 출현횟수는 1이 줄어들고, 7의 출현횟수도 1이 줄어듭니다.

1578 - [407, 1097, 518, 518, 518, 497, 418, 417, 408, 407]

1577 - [407, 1096, 518, 518, 518, 496, 418, 416, 407, 407]

 

그래서 1577의 답은 [407, 1096, 518, 518, 518, 496, 418, 416, 407, 407]가 됩니다.

 

이런 방식으로 답을 구하면 됩니다.

 

코드

n = int(input())
val = [*str(n)[::-1]]
new_val = ['9' for _ in range(len(val)-1)] + [val[-1]]
arr = []
for i in range(10):
    arr.append([10**i, i * int(10**(i-1))])
ans = [0] * 10
for i in range(len(new_val)):
    for j in range(int(new_val[i])):
        if i != 0:
            ans[j+1] += (int(new_val[i-1])+1) * 10 ** (i-1)
            for k in range(10):
                ans[k] += max(1, i * 10 ** (i-1))
        else: ans[j+1] += 1
for i in range(len(val)-2, -1, -1):
    for j in range(9, int(val[i]), -1):
        ans[j] -= arr[i][0]
        for k in range(len(val)-1, i, -1):
            ans[int(val[k])] -= arr[i][0]
        for k in range(10):
            ans[k] -= arr[i][1]
print(*ans)