백준(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억이라 시간 이내에 풀 수 없었다.  고민을 하던 중 백준님의 풀이를 참고해서 풀어보았다.

(링크: https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019?qid=9aa7818e-779e-499a-9c13-d2a5ac2ef8af&v=&b=&from_search=1)

풀이 :

문제를 변형해서 풀어보자.

일반적으로 순서대로 구하려면 시간내에 풀 수가 없으므로 

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;

}