백준(BOJ) 1019번 책 페이지
문제: https://www.acmicpc.net/problem/1019
지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.
풀이:
// 처음 시도 시간 초과
#include <iostream>
#include <cstring>
using namespace std;
int N;
int check[10];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(check, 0, sizeof(check));
cin >> N;
for (int i = 1; i <= N; ++i)
{
int num = i;
while (num != 0) {
check[num % 10]++;
num /= 10;
}
}
for (int i = 0; i < 10; ++i)
cout << check[i] << " ";
return 0;
}
N이 1억이 아닌 10억이라 시간 이내에 풀 수 없었다. 고민을 하던 중 백준님의 풀이를 참고해서 풀어보았다.
풀이 :
문제를 변형해서 풀어보자.
일반적으로 순서대로 구하려면 시간내에 풀 수가 없으므로
1부터 N까지의 숫자가 몇번 나오는지 구하기 에서 A에서 B까지 숫자가 몇번 나오는지로 문제를 변형해 보자.
단 A의 일의자리는 0으로 B의 일의 자리는 9로 바꿔준다. 아닐시 A++를 B--를 하여 맞춰준다.
예를들어 A = 1345이고 B = 8742 라면?
이렇게 하는 이유는? A = 1350 이고 B 가 = 8739 라면 일의 자리에 0~9는 ( 873 - 135 + 1) 씩임을 알 수 있기 떄문이다.
마찬가지로 A = 10 이고 B = 39 라면 일의 자리에 0~9는 ( 3 -1 + 1) 즉 3씩임을 알수 있듯이 동일하다.
일의 자리에 0~9를 구했으니 다음은 십의 자리에 0~9를 구해보자.
A = 135 B = 873 마찬가지로 0과 9로 맞춰준다.
A는 ++ 될떄 136, 137, 138, 139를 거쳐 140이 되는데 여기서 135 ~ 139 까지는 사실 1,3, 5~9 를 10번 거친 후 140이 되는 것이다.
( calc 를 거친다 )
A는 140, B는 869가 되었다.
그렇다면 0~9 까지는 ( 86-14 + 1 ) * 10씩이 될 것이다. 여기서는 십의 자리이기에 *10을 해주어야 한다.
다음 A는 14 B는 86 이므로 A는 20 B는 79로 맞춰주자.
0~9까지 각 (7 - 2 + 1 ) * 100 씩임을 알수있다.
다음 A는 2 B는 7이다.
A는 ++ 되면서 A == B 가 되기 때문에 종료한다.
코드 ( C ++ )
#include <iostream>
using namespace std;
// 0~ 9 의 값을 저장할 배열
long long check[10];
// ten은 자리 수(일의 자리, 십의자리 .. )
// calc함수는 n이라는 숫자에 나오는 0~9값을 check배열에 넣어준다.
void calc(long long n, long long ten)
{
while (n > 0) {
check[n % 10] += ten;
n /= 10;
}
}
void solve(long long A, long long B, long long ten) {
// A를 ++ 시키면서 0을 만든다.
while (A % 10 != 0 && A <= B)
{
// A를 ++ 시킬때는 calc를 거쳐야한다.
calc(A, ten);
A++;
}
if (A > B) return;
while (B % 10 != 9 && B >= A)
{
//B를 -- 시킬때는 calc를 거쳐야 한다.
calc(B, ten);
B--;
}
long long cnt = (B / 10 - A / 10 + 1);
//B-A +1 * 자리수 만큼 0~9에 각각 더해준다.
for (int i = 0; i < 10; ++i)
check[i] += cnt * ten;
// 다음자리 수를 계산위해 재귀함수 호출한다.
solve(A / 10, B / 10, ten * 10);
}
int main()
{
long long n;
cin >> n;
solve(1, n, 1);
for (int i = 0; i < 10; ++i)
cout << check[i] << " ";
return 0;
}
