백준 1019번

오늘 풀어본 문제는 백준의 1019번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

지민이는 전체 페이지의 수가 $N$ 인 책이 하나 있다. 첫 페이지는 $1$ 페이지이고, 마지막 페이지는 $N$ 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

입력

첫째 줄에 $N$ 이 주어진다. $N$ 은 $1,000,000,000$ 보다 작거나 같은 자연수이다.

출력

첫째 줄에 $0$ 이 총 몇 번 나오는지, $1$ 이 총 몇 번 나오는지, …, $9$ 가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

풀이과정

1번째 시도

수의 범위가 크기 때문에 각 수에서 숫자의 개수를 일일히 세는 방식으로는 해결할 수 없을 것이라고 생각하였다.

대신 떠올린 방법은 수의 범위를 분할해나가는 방식으로 전체 숫자의 개수를 세는 것이었다.

예를 들어, 페이지의 수가 $723456$ 이라고 하면 다음과 같이 분할과 셈을 한다.

1 ~ 723456

1 ~ 699999

- 1 ~ 99999

  	- 1 ~ 9999
        
      	- 1 ~ 999
            
          	- 1 ~ 99
                
              	- 1 ~ 9
                    
                  - 10 ~ 99
                    
                  	- 10 ~ 19
                        
                      - ...
                        
                      - 90 ~ 99
                
              - 100 ~ 999
                
              	- 100 ~ 199
                    
                  - ...
                    
                  - 900 ~ 999
            
          - 1000 ~ 9999
            
          	- 1000 ~ 1999
                
              - ...
                
              - 9000 ~ 9999
        
      - 10000 ~ 99999
        
      	- 10000 ~ 19999
            
          - ...
            
          - 90000 ~ 99999
    
  - 100000 ~ 199999
    
  - 200000 ~ 299999
    
  - 300000 ~ 399999
    
  - 400000 ~ 499999
    
  - 500000 ~ 599999
    
  - 600000 ~ 699999

700000 ~ 723456

- 맨 앞에 오는 7의 개수를 세어줌

  - 00000 ~ 23456
    
  	- 00000 ~ 19999
        
      	- 00000 ~ 09999
            
          - 10000 ~ 19999
        
      - 20000 ~ 23456
        
      	- 맨 앞에 오는 2의 개수를 세어줌
        
      	- 0000 ~ 3456
            
          	- 0000 ~ 2999
                
              	- 0000 ~ 0999
                    
                  - 1000 ~ 1999
                    
                  - 2000 ~ 2999
                
              - 3000 ~ 3456
                
              	- 맨 앞에 오는 3의 개수를 세어줌
                    
                  - 000 ~ 456
                    
                  	- 000 ~ 399
                        
                      	- 000 ~ 099
                            
                          - ...
                            
                          - 300 ~ 399
                        
                      - 400 ~ 456
                        
                      	- 맨 앞에 오는 4의 개수를 세어줌
                            
                          - 00 ~ 56
                            
                          	- 00 ~ 49
                                
                              	- 00 ~ 09
                                    
                                  - ...
                                    
                                  - 40 ~ 49
                                
                              - 50 ~ 56
                                
                              	- 맨 앞에 오는 5의 개수를 세어줌
                                    
                                  - 0 ~ 6

예제를 보면 특정 구간을 $X00\cdots\ \sim\ X99\cdots$ 와 $(X+1)00\cdots\ \sim\ ABC\cdots$ 형태로 쪼개는 방식을 재귀적으로 진행하여 숫자의 개수를 세어나감을 알 수 있다.

코드는 다음과 같이 작성하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

void update(vector<ull>& counts, ull N);
void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ull N;
	cin >> N;

	vector<ull> counts(10, 0);

	update(counts, N);

	for (ull i=0; i<10; i++) {
		cout << counts[i] << ' ';
	}

	return 0;
}

void update(vector<ull>& counts, ull N) {
	if (N == 0) {
		return ;
	}
	else if (N < 10) {
		for (ull i=1; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull digits = static_cast<ull>(log10l(N));
		ull powOf10 = static_cast<ull>(powl(10, digits));
		ull MSB = N / powOf10;

		update(counts, powOf10-1);
		for (ull i=1; i<MSB; i++) {
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		counts[MSB] += N - (MSB * powOf10) + 1;

		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1);
	}
}

void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits) {
	ull currentDigits = static_cast<ull>(log10l(N));

	if (currentDigits < digits) {
		counts[0] += (digits - currentDigits) * N;

		zeroPaddedUpdate(counts, N, currentDigits);
	}
	else if (N < 10) {
		for (ull i=0; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull powOf10 = static_cast<ull>(powl(10, digits));
		ull MSB = N / powOf10;

		for (ull i=0; i<MSB; i++) {
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		counts[MSB] += N - (MSB * powOf10) + 1;

		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1);
	}
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

코드를 살펴보다가 혹시 zeroPaddedUpdate 함수에서 currentDigits 를 구하는 과정에서 $N$ 이 $0$ 일 때 오작동을 일으키나 싶어 따로 처리해주기로 했다.

코드는 다음과 같이 수정하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

void update(vector<ull>& counts, ull N);
void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ull N;
	cin >> N;

	vector<ull> counts(10, 0);

	update(counts, N);

	for (ull i=0; i<10; i++) {
		cout << counts[i] << ' ';
	}

	return 0;
}

void update(vector<ull>& counts, ull N) {
	if (N == 0) {
		return ;
	}
	else if (N < 10) {
		for (ull i=1; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull digits = static_cast<ull>(log10l(N));
		ull powOf10 = static_cast<ull>(powl(10, digits));
		ull MSB = N / powOf10;

		update(counts, powOf10-1);
		for (ull i=1; i<MSB; i++) {
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		counts[MSB] += N - (MSB * powOf10) + 1;

		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1);
	}
}

void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits) {
	ull currentDigits = static_cast<ull>(log10l(N));

	if (N == 0) {
		counts[0] += digits + 1;
	}
	else if (currentDigits < digits) {
		counts[0] += (digits - currentDigits) * N;

		zeroPaddedUpdate(counts, N, currentDigits);
	}
	else if (N < 10) {
		for (ull i=0; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull powOf10 = static_cast<ull>(powl(10, digits));
		ull MSB = N / powOf10;

		for (ull i=0; i<MSB; i++) {
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		counts[MSB] += N - (MSB * powOf10) + 1;

		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1);
	}
}

실행 결과 ‘틀렸습니다’ 가 떴다.

3번째 시도

내가 임의로 정한 $723456$ 를 이용하여 함수들의 로직을 따라가면서 주석을 달며 의도한대로 작동하는지 확인해본 결과, zeroPaddedUpdate 함수에서 $N$ 이 아닌 $N+1$ 을 곱해야 하는 부분을 발견했다.

코드는 다음과 같이 수정하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

void update(vector<ull>& counts, ull N);
void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ull N;
	cin >> N;

	vector<ull> counts(10, 0);

	update(counts, N);

	for (ull i=0; i<10; i++) {
		cout << counts[i] << ' ';
	}

	return 0;
}

void update(vector<ull>& counts, ull N) { // Example: 723456
	if (N == 0) {
		return ;
	}
	else if (N < 10) {
		for (ull i=1; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull digits = static_cast<ull>(log10l(N)); // 5
		ull powOf10 = static_cast<ull>(powl(10, digits)); // 100000
		ull MSB = N / powOf10; // 7

		update(counts, powOf10-1); // 1 ~ 99999
		for (ull i=1; i<MSB; i++) { // 100000 ~ 199999, 200000 ~ 299999, ..., 600000 ~ 699999
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		// 700000 ~ 723456
		counts[MSB] += N - (MSB * powOf10) + 1;
		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1); // 00000 ~ 23456
	}
}

void zeroPaddedUpdate(vector<ull>& counts, ull N, ull digits) { // Example: 23456
	ull currentDigits = static_cast<ull>(log10l(N)); // 4

	if (N == 0) { // Example: 00000
		counts[0] += digits + 1;
	}
	else if (currentDigits < digits) { // Example: 00234
		counts[0] += (digits - currentDigits) * (N + 1); 

		zeroPaddedUpdate(counts, N, currentDigits);
	}
	else if (N < 10) {
		for (ull i=0; i<=N; i++) {
			counts[i]++;
		}
	}
	else {
		ull powOf10 = static_cast<ull>(powl(10, digits)); // 10000
		ull MSB = N / powOf10; // 2

		for (ull i=0; i<MSB; i++) { // 00000 ~ 09999, 10000 ~ 19999
			counts[i] += powOf10;

			for (ull j=0; j<10; j++) {
				counts[j] += powOf10 * digits / 10;
			}
		}

		// 20000 ~ 23456
		counts[MSB] += N - (MSB * powOf10) + 1; 
		zeroPaddedUpdate(counts, N - (MSB * powOf10), digits-1); // 0000 ~ 3456
	}
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

수들의 구간을 분할하는 아이디어를 떠올리는 것 자체는 어렵진 않았지만, 이를 실제로 구현하는게 빡센 문제였다. 복잡한 수학 지식을 요구하지 않아도 Platinum V 난이도를 받을 수 있다는 걸 보여주는 매콤한 문제였던 것 같다…

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1019

← Previous Post Next Post →