[PS] BOJ 1019(책 페이지) - C++

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

1019번: 책 페이지

 

10의 자릿수가 변할 때마다, 1의 자리 0~9까지가 반복된다. 또한, 100의 자릿수가 변할 때마다, 0~99의 숫자가 반복된다. 

즉, 각 자릿수마다 특정 패턴들이 반복된다.

 

각 자릿수 별로 등장하는 패턴들을 예시를 통해 살펴보자. 

N이 32698723이라고 가정하고, $10^6$의 자릿수에서의 숫자들의 등장 횟수를 살펴보자.

경우의 수는 다음과 같이 나누어진다. 

• N의 $10^6$자릿수보다 작은 경우 
• N의 $10^6$자릿수보다 큰 경우
• N의 $10^6$자릿수와 같은 경우 

 

작은 경우

N = 32698723이고,

$10^6$자릿수에서 5의 등장 횟수를 살펴보자. 

 

우선, A5B의 형태에서 

B의 자리에는 00000 ~ 99999까지 올 수 있다. 즉, $10^5$개가 존재한다. 

이러한 패턴은 A 자리에는 0~32까지 올 수 있다. 즉, B의 자리의 패턴이 총 0~32까지 반복된다. 

$33 * 10^5$

 

큰 경우 

N = 32698723이고,

$10^6$자릿수에서 7의 등장 횟수를 살펴보자. 

 

A7B의 형태에서, 

마찬가지로 B의 자리에는 최대 $10^5$개가 올 수 있다. 

하지만, A 자리에는 0~31까지만 가능하다. 

(327XXXXX > 32698723)

$32 * 10^5$

 

같은 경우

N = 32698723이고,

$10^6$자릿수에서 6의 등장 횟수를 살펴보자. 

 

A6B의 형태에서 "큰 경우"와 마찬가지로

A 자리에는 0~31까지 B의 자리에 최대 $10^5$개가 올 수 있다. 

 

또한, 추가로 A = 32이 일 때는 0~98723까지 총 98724개가 가능하다. 

$32 * 10^5 + 98724$

 

일반화 

위의 식을 일반화를 해보자. 

N이라는 숫자의 $10^i$자릿수는 $N_i$라고 가정하자. (단, $i$는 양의 정수)

이때, $10^i$번째에 $K_i$라는 숫자가 나오는 경우의 수는 다음과 같이 정의된다.

 

이를 코드로 표현하면 다음과 같다. 

void solve(int n) {
	string str = to_string(n);
	
	int apperance = 1; // 10 ^ {i-1}  위의 식에서 B에 해당되는 부분
	int temp = n;
	
	for(int i = 0; i < str.size()-1; i++, apperance*=10) {
		for(int j = 0; j <= 9; j++) {
			int num = temp % 10; // 10^i번째 대소관계를 위한 숫자.
			int cnt = temp / 10; // 위의 식에서 A에 해당 되는 곳
			
			if(j < num) cnt ++; // 작은 경우
			if(j == num) totalAppearance[j] += (n % apperance + 1); // 같은 경우

			totalAppearance[j] += (cnt * apperance);
		}
		temp /= 10;
	}
	
	int last = str[0] - '0';
	for(int i = 1; i <= last; i++) {
		if(i < last) totalAppearance[i] += (apperance);
		else totalAppearance[i] += (n % apperance + 1);
	}
}

 

마지막의 코드는 N에서 제일 큰 자릿수에서의 경우의 수이다. 해당 경우에는 A의 자릿수가 항상 0이기 때문에 따로 처리해 주었다. 

 

예외 처리

하지만, 0에서는 다음과 같은 예외가 존재한다. 

A0B를 살펴보자.  

해당 경우에는 B에서는 위에서 살펴본 경우와 같지만, A에서 0은 들어갈 수 없다. 

즉, 0인 경우는 1~32까지이기에, cnt를 감소시켜주어야 한다. 

if(j < num) cnt ++;
if(j == 0)  cnt --;

 

 

전체 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'

int totalAppearance[10];

void solve(int n) {
	string str = to_string(n);
	
	int apperance = 1;
	int temp = n;
	
	for(int i = 0; i < str.size()-1; i++, apperance*=10) {
		for(int j = 0; j <= 9; j++) {
			int num = temp % 10;
			int cnt = temp / 10;
			
			if(j < num) cnt ++;
			if(j == 0) cnt --;
			if(j == num) totalAppearance[j] += (n % apperance + 1);

			totalAppearance[j] += (cnt * apperance);
		}
		temp /= 10;
	}
	
	int last = str[0] - '0';
	for(int i = 1; i <= last; i++) {
		if(i < last) totalAppearance[i] += (apperance);
		else totalAppearance[i] += (n % apperance + 1);
	}
}

int main() {
	FAST;
	int N; cin >> N;
	solve(N);
	for(int i = 0; i < 10; i++) cout << totalAppearance[i] << " ";
}