문제:
지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.
입력:
첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
출력:
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
풀이방법:
0부터 9까지는 각 숫자가 한번씩 나온다는 사실을 사용해서 이 문제를 해결한다.
예를 들어 N이 99로 주어진다면 일의 자리만 보았을 때, 0~9가 총 10번 나타나고, N이 29로 주어진다면 0~9는 총 3번 등장할 것이다. 즉, 십의 자리에 따라서 나오는 횟수가 달라지게 된다.
일의 자리가 아닌 다른 자릿수도 그와 유사하게 구할 수 있다. 다만 각 자릿수에 따른 배수를 고려해야 한다. 19의 경우 십의 자리만 봤을 때, 10~19까지 1이 총 10번 등장하는 것을 알 수 있다. 즉 각 자릿수에 따라 1배, 10배, 100배, ... 만큼의 갯수가 존재한다고 생각하면 된다.
0~9의 틀을 고정하기 위해서 매 N의 일의 자리를 9로 고정시켜주도록 한다. N이 121일 때의 예시로 코드가 돌아가는 것을 확인해본다.
우선 121의 일의 자릿수를 9로 만들기 위해 121, 120만 따로 계산해주도록 한다. 이 과정이 끝나면 N=119가 되고, answer는 [1, 3, 2, 0, 0, 0, 0, 0, 0, 0]가 된다.
119에서 일의 자리에서 0~9는 총 12번 나타나게 된다. 따라서 각 answer에 12를 더해주고, 책 페이지의 시작은 1이기 때문에 0의 자릿수만 하나 빼주도록 한다. 이 과정이 끝나면 N=11이 되고, answer는 [12, 15, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.
N = 11이기 때문에 9로 만들어주도록 한다. 11과 10만 따로 계산을 진행하며, 이 때 배수는 10이기 때문에 N=9, answer는 [22, 45, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.
십의 자리에서 0~9가 총 1*10번 나타나게 된다. 따라서 각 answer에 10을 더해주고, 십의 자리에서 0은 존재할 수 없기 때문에 0의 자릿수만 빼주도록 한다. (01, 02, 03, ... 은 존재하지 않음)
따라서 최종적으로 22 55 24 22 22 22 22 22 22 22 의 값을 가지게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def add(x,answer,multiply):
while x > 0:
answer[x%10]+=multiply
x//=10
N = int(input())
answer = [0]*10
tmp_number = []
multiply = 1
while 1 <= N:
if N%10 !=9:
add(N,answer,multiply)
N-=1
continue
if N < 1:
break
N//=10
for j in range(10):
answer[j] += (N+1) * multiply
answer[0]-=multiply
multiply*=10
print(*answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1019
1019번: 책 페이지
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ] 21608. 상어 초등학교 (0) | 2021.10.06 |
|---|---|
| [BOJ] 10157. 자리배정 (0) | 2021.10.05 |
| [BOJ]3020. 개똥벌레 (0) | 2021.09.30 |
| [BOJ]6593. 상범 빌딩 (0) | 2021.09.29 |
| [BOJ]12904. A와 B (0) | 2021.09.28 |