- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
👀 [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
- [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
- [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
- [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
- [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
- [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
Table of Contents
책 페이지 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 128MB |
문제 🔗
지민이는 전체 페이지의 수가 인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.
입력 🔗
첫째 줄에 이 주어진다. 은 보다 작거나 같은 자연수이다.
출력 🔗
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 11 |
- 출력
TC
0 | 1 4 1 1 1 1 1 1 1 1 |
풀이 🔗
문제는 명확하고 직관적이다. 1페이지부터 페이지까지 나열할 때, 숫자가 사용된 수를 각 숫자별로 나타내는 문제.
165라는 숫자를 표기하기 위해선 이 사용된다. 이렇게 1부터 해당 숫자까지의 모든 숫자를 표현하기 위해 사용한 숫자의 수를 0부터 오름차순으로 출력하면 된다.
즉, 라고 가정하면, 페이지 배열은 까지 나열된다. 각 숫자가 사용된 수를 표로 나타내면 아래와 같다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
1부터 5까지 나열하는데, 각각 숫자 하나씩 사용했으니 위 처럼 표시할 수 있다. 그렇다면 예제의 11은 어떨까?
까지 나열된다.
1부터 9까지는 각각 숫자가 하나씩 사용되며, 10은 1과 0이 사용되고, 11은 1이 두 개 사용된다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
위의 표만큼 숫자가 사용됐다. 이해를 위해 일 경우를 하나 더 해보자.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
, 이 된다. 1 ~ 13에는 11도 포함되기 때문에, 11의 결과에 12, 13의 값을 각각 더해줘도 상관없다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 6 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
이 정도면 알고리즘이 원하는 게 무엇인지 이해했으리라 생각한다.
🔎규칙 찾아보기 🔗
사실 무식하게 접근하면, 그리 어려운 문제는 아니다. 하나하나 반복문 돌려가며 숫자 분해해서 해당하는 숫자의 배열에 집어넣으면 그만이니. 하지만 안타깝게도, 변수 의 최대값은 10억 ~~(다행히 int의 최대값은 넘지 않는다.)~~ 에 육박한다. 그 말인즉는 무식하게 접근하면 안 된다는 의미.
그렇다면 어딘가에 존재하는 규칙성을 발견해서 일반식을 설계해야한다는 뜻인데, 이럴땐 하나하나 나열해보면 알 수 있을 것이다.
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
5 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
6 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
8 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
9 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
10 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
11 | 1 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
12 | 1 | 5 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
13 | 1 | 6 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
14 | 1 | 7 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
15 | 1 | 8 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 |
16 | 1 | 9 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
17 | 1 | 10 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 |
18 | 1 | 11 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
19 | 1 | 12 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
20 | 2 | 12 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
21 | 2 | 13 | 4 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
22 | 2 | 13 | 6 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
23 | 2 | 13 | 7 | 3 | 2 | 2 | 2 | 2 | 2 | 2 |
규칙성을 찾아보기 위해 20 받고 살짝 더 얹어서 사용된 숫자를 나열해보았다. 어떤 패턴이 보이는 것 같긴 하다.
- 0은 10의 배수마다 1씩 증가한다.
- 각 1의 자리마다 해당하는 숫자가 1씩 증가하며, 값은 10의 자릿수 + 1이다.
- 10의 자릿수는 해당하는 숫자를 1씩 증가시킨다.
그냥 쳐다보면 규칙성을 찾기 좀 어려울 수 있다. 해답은 *0 ~ *9 구간에 있다. 예를 들어, 10 ~ 29까지 나열해보자. 1부터 시작하는 것이 아니라, 임의의 구간 를 기준으로 알고리즘을 계산한다고 가정하는 것이다.
숫자 현황 | |||||||||
---|---|---|---|---|---|---|---|---|---|
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
위 표의 숫자들을 잘 보면, 1의 자리 숫자는 각각 하나씩 사용하는 것을 확인할 수 있다.
1의 자리에서의 규칙 🔗
숫자 현황 | |||||||||
---|---|---|---|---|---|---|---|---|---|
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
이제 좀 규칙성이 눈에 띄기 시작한다. 20 ~ 39와 같은 *0 ~ *9 형태의 범위에선 1의 자리에 해당하는 모든 숫자가 동일하게 사용된다. 10 ~ 19, 20 ~ 29 두 구간이 있으므로 각 구간별로 1씩 모든 숫자가 두 번 사용됐다.
시작 페이지를 , 마지막 페이지를 이라고 가정할 때, 위 규칙을 일반식으로 표현하면 아래와 같다.
따라서 10 ~ 29 범위에서 모든 숫자는 두 번 사용된 것임을 알 수 있다.
p의 자리에서의 규칙 🔗
문제는 위 식은 1의 자리에서만 적용되는 수식이다. 페이지는 최대 10의 자리까지 존재할 수 있다. 즉, 통용되는 일반식을 구해야한다.
숫자 현황 | |||||||||
---|---|---|---|---|---|---|---|---|---|
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
반대로 10의 자리수를 자세히 보자. 1이 10번 사용된다. 만약 100 ~ 199 구간이라면 1은 100개가 사용될 것이고, 1000 ~ 1999 구간이라면 1은 1000개가 사용될 것이다.
쉽게 설명하기 위해 10 ~ 19, 100 ~ 199, 1000 ~ 1999 등 같은 형태의 구간을 단위 구간이라고 정의하자. 이 때, 해당 구간에서 이 사용되는 갯수는 아래와 같이 정의할 수 있다.
- : 구간 시작 값
- : 구간 끝 값
- : 자릿수
구간 보정하기 🔗
이제 구간만 맞으면 호출되는 숫자를 구할 수는 있지만, 아직 제한적이다.
우선, 본 알고리즘에서 시작 값은 1로 고정이다. 끝 값인 역시 반드시 199와 같은 단위 구간의 형태로 들어오지도 않는다. 만약 라면 우리는 1 ~ 35 구간에 알고리즘을 적용해야 한다. 구간이 10 ~ 39라면 모를까, 형태가 전혀 다른 구간에는 위 일반식이 적용되지 않는다.
해결 방법은 간단하다. 가늠좌 클리크 조정하듯이 구간에 맞게 값을 더하고 빼서 조정해주면 된다.
1 ~ 35 구간에서, 1의 경우, 1보다 크며 0을 포함한 수 중 가장 가까운 값은 10이다. 따라서, 시작 값은 10까지 증가시키며, 증가시킨 숫자를 카운팅한다. 1부터 9까지 카운팅되므로, 이를 표로 표현하면 아래와 같다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
35의 경우 35보다 작으며 9를 포함한 수 중 가장 가까운 수는 29다. 마찬가지로 마지막 값은 29까지 감소시키며, 감소한 숫자를 카운팅한다. 35부터 30까지 카운팅되므로, 이를 표로 표현하면 아래와 같다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 7 | 1 | 1 | 0 | 0 | 0 | 0 |
즉, 초기값은 위 보정값을 더한 배열이며, 이후 계산은 계산된 초기값에 누적한다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 7 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 2 | 2 | 8 | 2 | 2 | 1 | 1 | 1 | 1 |
자릿수 보정하기 🔗
, 일 때, 1의 자리에 사용된 숫자의 갯수를 구하면 아래와 같다.
1의 자리에서 각 숫자는 100개씩 사용됐다. 10의 자리에서는 어떨까?
, 을 각각 10으로 나누면 10의 자리에 대한 구간을 얻을 수 있다. 나눠진 숫자를 위의 일반식에 적용하면 된다.
100의 자리는 , 을 각각 100으로 나누어 계산하면 된다.
1000의 자리는 , 을 각각 1000으로 나누어 계산하면 된다. 그러나 이므로, 1에만 1000개가 사용된다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
1 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
10 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
1000 | 0 | 1000 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
300 | 1300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 |
따라서 1000 ~ 1999 구간은 위와 같이 계산된다.
📃일반식 적용하기 🔗
완벽한 이해를 위해, 위 개념을 토대로 일 경우의 알고리즘을 계산해보자.
이므로, 구간은 1 ~ 4153이다.
시작 페이지 구간 보정하기 🔗
1보다 큰 수 중 1의 자리가 0인 가장 가까운 수 10까지 이동하며, 이동한 수를 별도로 카운팅한다.
1부터 9까지 이동하여 10에 도착하므로, 1 ~ 9를 별도로 카운팅해준다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 ~ 9 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
마지막 페이지 구간 보정하기 🔗
4153보다 작은 수 중 1의 자리가 9인 가장 가까운 수 4149까지 이동하며, 이동한 수를 별도로 카운팅한다.
4153부터 4150까지 이동하여 4149까지 도착하므로, 이를 별도로 카운팅해준다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
4153 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
4152 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
4151 | 0 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
4150 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
1의 자리 일반식 적용 🔗
일반식을 적용할 수 있는 구간 10 ~ 4149을 구했으니, 일반식을 적용한다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1의 자리 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 |
10의 자리 구간 계산 및 보정하기 🔗
상위 자릿수 계산을 위해 1의 자리 일반식 구간 4149, 10을 각각 10으로 나눈다.
10의 자리에 대한 구간은 가 된다. 마찬가지로 일반식 적용을 위해 구간을 보정한다. 10의 자리이므로, 1 -> 2로의 이동은 실제로 10 -> 20으로의 이동임에 주의하자.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 ~ 9 | 0 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
414 | 0 | 10 | 0 | 0 | 20 | 0 | 0 | 0 | 0 | 0 |
413 | 0 | 10 | 0 | 10 | 10 | 0 | 0 | 0 | 0 | 0 |
412 | 0 | 10 | 10 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
411 | 0 | 20 | 0 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
410 | 10 | 10 | 0 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
10의 자리 일반식 적용 🔗
일반식을 적용할 수 있는 구간 10 ~ 409를 구했으니, 일반식을 적용한다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
10의 자리 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 |
100의 자리 구간 계산 및 보정하기 🔗
상위 자릿수 계산을 위해 10의 자리 일반식 구간 409, 10을 각각 10으로 나눈다.
100의 자리에 대한 구간은 이 된다. 나머지는 10의 자리 프로세스와 동일하다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 ~ 9 | 0 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
40 | 100 | 0 | 0 | 0 | 100 | 0 | 0 | 0 | 0 | 0 |
100의 자리 일반식 적용 🔗
일반식을 적용할 수 있는 구간 10 ~ 39를 구했으니, 일반식을 적용한다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
10의 자리 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 |
1000의 자리 구간 계산 및 보정하기 🔗
상위 자릿수 계산을 위해 100의 자리 일반식 구간 39, 10을 각각 10으로 나눈다.
1000의 자리에 대한 구간은 이 된다.
여기서 문제가 하나 있는데, 마지막 구간에서 일의 자리가 9인 가장 작은 수는 -9다. 음수가 올 수 없으므로, 더 이상의 일반식 연산은 불가능하며, 개별적으로 더해주면 된다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 ~ 3 | 0 | 1000 | 1000 | 1000 | 0 | 0 | 0 | 0 | 0 | 0 |
총합 계산하기 🔗
단계별로 구한 숫자를 정리하여 총합을 표로 나타낸다.
구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 ~ 9 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4153 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
4152 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
4151 | 0 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
4150 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
1의 자리 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 | 414 |
1 ~ 9 | 0 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
414 | 0 | 10 | 0 | 0 | 20 | 0 | 0 | 0 | 0 | 0 |
413 | 0 | 10 | 0 | 10 | 10 | 0 | 0 | 0 | 0 | 0 |
412 | 0 | 10 | 10 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
411 | 0 | 20 | 0 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
410 | 10 | 10 | 0 | 0 | 10 | 0 | 0 | 0 | 0 | 0 |
10의 자리 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 | 400 |
1 ~ 9 | 0 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
40 | 100 | 0 | 0 | 0 | 100 | 0 | 0 | 0 | 0 | 0 |
10의 자리 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 |
1 ~ 3 | 0 | 1000 | 1000 | 1000 | 0 | 0 | 0 | 0 | 0 | 0 |
총합 | 1225 | 2290 | 2236 | 2236 | 1389 | 1229 | 1225 | 1225 | 1225 | 1225 |
구간 1 ~ 4153에 대한 알고리즘 결과는 위와 같다.
전체 소스 🔗
JAVA
0 | import java.io.BufferedReader; |
1 | import java.io.BufferedWriter; |
2 | import java.io.IOException; |
3 | import java.io.InputStreamReader; |
4 | import java.io.OutputStreamWriter; |
5 | |
6 | /** |
7 | * 백준 전체 1019 문제 알고리즘 클래스 |
8 | * |
9 | * @author RWB |
10 | * @see <a href="https://blog.itcode.dev/posts/2021/06/28/a1019">1019 풀이</a> |
11 | * @since 2021.06.28 Mon 12:28:50 |
12 | */ |
13 | public class Main |
14 | { |
15 | // 숫자 카운트 배열 |
16 | private static final int[] COUNTER = new int[10]; |
17 | |
18 | /** |
19 | * 메인 함수 |
20 | * |
21 | * @param args: [String[]] 매개변수 |
22 | * |
23 | * @throws IOException 데이터 입출력 예외 |
24 | */ |
25 | public static void main(String[] args) throws IOException |
26 | { |
27 | BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); |
28 | BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); |
29 | |
30 | // 마지막 페이지 |
31 | int N = Integer.parseInt(reader.readLine()); |
32 | |
33 | solve(N); |
34 | |
35 | StringBuilder builder = new StringBuilder(); |
36 | |
37 | for (int item : COUNTER) |
38 | { |
39 | builder.append(item).append(" "); |
40 | } |
41 | |
42 | writer.write(builder.toString().trim()); |
43 | writer.newLine(); |
44 | writer.flush(); |
45 | |
46 | reader.close(); |
47 | writer.close(); |
48 | } |
49 | |
50 | /** |
51 | * 알고리즘 동작 함수 |
52 | * |
53 | * @param num: [int] 마지막 페이지 |
54 | */ |
55 | private static void solve(int num) |
56 | { |
57 | // 시작 페이지 |
58 | int start = 1; |
59 | |
60 | // 자릿수 |
61 | int digit = 1; |
62 | |
63 | while (start <= num) |
64 | { |
65 | // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함 |
66 | while (num % 10 != 9 && start <= num) |
67 | { |
68 | // 감소한 페이지 별도 카운팅 |
69 | count(num, digit); |
70 | |
71 | num--; |
72 | } |
73 | |
74 | // 마지막 페이지가 시작 페이지보다 작을 경우 |
75 | if (num < start) |
76 | { |
77 | // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐 |
78 | break; |
79 | } |
80 | |
81 | // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함 |
82 | while (start % 10 != 0 && start <= num) |
83 | { |
84 | // 증가한 페이지 별도 카운팅 |
85 | count(start, digit); |
86 | |
87 | start++; |
88 | } |
89 | |
90 | start /= 10; |
91 | num /= 10; |
92 | |
93 | for (int i = 0; i < 10; i++) |
94 | { |
95 | COUNTER[i] += (num - start + 1) * digit; |
96 | } |
97 | |
98 | // 자릿수 증가 |
99 | digit *= 10; |
100 | } |
101 | } |
102 | |
103 | /** |
104 | * 카운트 함수 |
105 | * |
106 | * @param num: [int] 대상 숫자 |
107 | * @param digit: [int] 자릿수 |
108 | */ |
109 | private static void count(int num, int digit) |
110 | { |
111 | while (num > 0) |
112 | { |
113 | COUNTER[num % 10] += digit; |
114 | num /= 10; |
115 | } |
116 | } |
117 | } |
일 때, 구간을 보정하는 과정에서 4153, 4152와 같은 수를 별도로 카운팅해야한다.
JAVA
0 | /** |
1 | * 카운트 함수 |
2 | * |
3 | * @param num: [int] 대상 숫자 |
4 | * @param digit: [int] 자릿수 |
5 | */ |
6 | private static void count(int num, int digit) |
7 | { |
8 | while (num > 0) |
9 | { |
10 | counter[num % 10] += digit; |
11 | num /= 10; |
12 | } |
13 | } |
로직은 어렵지 않다. 4152의 경우 로 이루어져있으므로, 해당하는 숫자에 자릿수만큼 카운팅(1이면 1개, 10이면 10개)하면 된다.
1의 자리는 와 같이 구할 수 있다. 10의 자리는 4152를 10으로 한 번 나누고 방금의 연산을 다시 진행하면 된다.
100, 1000 등 자릿수만큼 반복하여 계산하면 된다.
JAVA
0 | /** |
1 | * 알고리즘 동작 함수 |
2 | * |
3 | * @param num: [int] 마지막 페이지 |
4 | */ |
5 | private static void solve(int num) |
6 | { |
7 | // 시작 페이지 |
8 | int start = 1; |
9 | |
10 | // 자릿수 |
11 | int digit = 1; |
12 | |
13 | while (start <= num) |
14 | { |
15 | // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함 |
16 | while (num % 10 != 9 && start <= num) |
17 | { |
18 | // 감소한 페이지 별도 카운팅 |
19 | count(num, digit); |
20 | |
21 | num--; |
22 | } |
23 | |
24 | // 마지막 페이지가 시작 페이지보다 작을 경우 |
25 | if (num < start) |
26 | { |
27 | // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐 |
28 | break; |
29 | } |
30 | |
31 | // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함 |
32 | while (start % 10 != 0 && start <= num) |
33 | { |
34 | // 증가한 페이지 별도 카운팅 |
35 | count(start, digit); |
36 | |
37 | start++; |
38 | } |
39 | |
40 | start /= 10; |
41 | num /= 10; |
42 | |
43 | for (int i = 0; i < 10; i++) |
44 | { |
45 | counter[i] += (num - start + 1) * digit; |
46 | } |
47 | |
48 | // 자릿수 증가 |
49 | digit *= 10; |
50 | } |
51 | } |
시작 페이지는 무조건 1로 고정이다. 시작 페이지가 마지막 페이지보다 커질 때까지 반복한다.
첫 번째 while
문에서 마지막 페이지를 1씩 감소시켜 9로 끝나는 구간으로 보정한다. 중간에 조건문이 있는데, 이 처리를 해주지 않으면 num
이 9보다 작을 경우 연산 과정에서 start
가 num
을 초과하지 못해 무한루프를 타게 된다.
두 번째 while
문은 1페이지를 1씩 증가시켜 0으로 끝나는 구간으로 보정한다. 보정된 모든 값은 count
메소드를 통해 별도로 카운팅된다.
위 과정을 통해 구간을 맞췄으니, 나머지는 위에 언급한 수식을 적용하고, 이를 반복한다.
분류 🔗
- 수학
📆 작성일
2021-06-28 Mon 12:28:50
📚 카테고리
🏷️ 태그