https://www.acmicpc.net/problem/1019
1019번: 책 페이지
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
www.acmicpc.net
[ 문제풀이 ]
책의 페이지가 N이라고 할 때 1~N까지 0 ~ 9가 몇 번 나오는지 출력하는 문제입니다. N의 최댓값이 1,000,000,000이므로 모든 숫자를 탐색하면 시간 초과가 나므로 구간을 정해 답을 구하는 방법을 통해 문제를 풀었습니다.
A ~ B까지 숫자 중 0 ~ 9까지의 숫자가 몇번 나오는지 구하는 방법은 다음과 같습니다.
A는 일의 자리가 0이 되어야하고, B는 일의 자리가 9가 되어야 합니다. 그러기 위해서 A는 값을 더해주어 일의 자리를 0으로 맞춰주고, B는 값을 빼주어 일의 자리를 9로 맞춰줍니다.
A = 1345, B = 8742 라고 할 때, A에는 값을 더해주어 1350으로 만들고, B에는 값을 빼주어 8739로 맞춰줍니다. 이때 A부터 B까지 일의 자리에 0~9는 총 (8739 / 10 - 1350 / 10 + 1)번 등장합니다. 즉, (873 - 135 + 1)번 등장합니다. 그리고 1345~1349, 8740~8742까지 0~9이 몇 번 나오는지 따로 체크해주어야 합니다.
이제 일의 자리에 0~9가 몇 번 나오는지 구했습니다. 다음으로 십의 자리에 0~9가 몇번 나오는지 구해보겠습니다.
이때 A = 135, B = 873 입니다. 똑같은 방식을 적용하면 A = 140, B = 869로 바꾸어주고, 이 때 0~9는 (86 - 14 + 1)번 나올까요? 아닙니다!! 십의 자리 숫자이기 때문에 10을 곱해주어야 합니다. 따라서 (86 - 14 + 1) * 10을 각각 더해주면 됩니다.
똑같은 방식으로 천의 자리, 만의 자리 등등 구해주시면 됩니다.
다만 A = 7, B = 15 일 때, 똑같은 방식을 적용하면 A = 10, B = 9가 되므로 A의 값이 더 커지게 됩니다. 이 때는 B + 1부터 15까지의 0~9의 개수를 구해주고, A/10( = 1)부터 9까지 다시 구해주시면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include<iostream> #include<string> using namespace std; int N; int cnt[10]; int NtoA(int num) //num보다 작은 가장 큰 10^n 수 { int digit = 1; while (1) { digit *= 10; if (num < digit) { return digit / 10; } } } int NtoB(int num) //num보다 작은 가장 큰 9로 끝나는 수 { if (num < 9) { return num; } while (1) { if (num % 10 == 9) { return num; } num--; } } void AtoN(int A, int N, int digit) //A부터 N까지의 수의 1의 자리 숫자의 개수 구하기 { if (N < 10) { for (int i = A; i <= N; i++) { cnt[i] += digit; } return; } int B = NtoB(N); for (int i = B + 1; i <= N; i++) { string str = to_string(i); for (int j = 0; j < str.size(); j++) { cnt[str[j] - '0'] += digit; } } for (int i = 0; i < 10; i++) { cnt[i] += (B / 10 - A / 10 + 1) * digit; } AtoN(A / 10, B / 10, digit * 10); } int main() { cin >> N; int A = NtoA(N); int B = NtoB(N); if (A > B) { for (int i = B + 1; i <= N; i++) { string str = to_string(i); for (int j = 0; j < str.size(); j++) { cnt[str[j] - '0']++; } } A /= 10; AtoN(A, B, 1); } else { AtoN(A, N, 1); } while (1) { if (A == 1) { break; } AtoN(A / 10, A - 1, 1); A /= 10; } for (int i = 0; i < 10; i++) { cout << cnt[i] << " "; } } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 2357번 - 최솟값과 최댓값 (C++) (0) | 2022.07.05 |
|---|---|
| [ 백준 ] 2042번 - 구간 합 구하기 (C++) (0) | 2022.07.04 |
| [ 백준 ] 17436번 - 소수의 배수 (C++) (0) | 2022.07.02 |
| [ 백준 ] 16565번 - N포커 (C++) (0) | 2022.07.01 |
| [ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++) (0) | 2022.06.30 |