백준 No.1019 [책 페이지]

BOJ No.1019 [책 페이지]

---

  문제 

1019번: 책 페이지 (acmicpc.net)

1019번: 책 페이지

---

  설명 

 <알고리즘 분류> 
 * 수학

 

  숫자의 영역을 3개로 나누어 카운팅을 한다.

  위 예시는 입력값이 8853 인 경우이다. 처음에 값을 입력 받으면, 위 예시처럼 입력된 숫자와 가장 가까운 9로만 이루어진 더 작은 숫자를 찾는다. 위 경우에는 999 가 이에 해당된다. 이 숫자를 기점으로 first area, second area 로 나뉘게 된다. 그리고, 9로 끝나는 가장 가까운 수를 찾는다. 이 숫자를 기점으로 second area, last area 로 나뉘게 된다.

 

first area

  1 ~ 99..99 영역에 해당되는 부분이다. 1 ~ 9 /  1 ~ 99 / 1 ~ 999 / 1 ~ 9,999 ... 등이 된다. 이 영역들에는 규칙이 있다. 만약 최대 숫자의 길이가 k 라면 이 영역 내에 숫자들의 개수는 아래와 같다.

 

• 0의 개수 : k * (10 ^ (k - 1)) - [1로만 이루어진 k자리 숫자]
• 1 ~ 9 의 개수 : k * (10 ^ (k - 1))

 

second area

  이 영역에서 첫 번째 자리 부분의 0 ~ 9 숫자들은 모두 동일한 개수이다. 쉬운 예시로 10 ~ 59 영역에서 첫 번째 자리에서 0 ~ 9 부분은 총 5번 반복되므로 5개씩 존재한다.

 

  위 예시 표에서 k의 값은 입력된 숫자의 k 번째 자리수에 숫자들을 세는 것 이다. (k 값은 second area 에만 적용된다) 또한 현재의 second area 는 그 영역의 끝에 해당되는 두 값에서 첫 번째 자리수를 날리고 ( n /= 10 ) 다음 작업의 second area, last area 가 된다. 이전에 설명한 방식으로 다시 한 번 second area, last area로 나뉘는 것 이다. 하지만 위 예시에서 k 가 4인 경우, second area, last area 로 영역을 나눌 수 없게 된다. 이 경우에는 그 영역에 있는 숫자들의 개수에 모두 10 ^ (k - 1) 을 더하면 된다. second area 의 식은 아래와 같다.

 

• 0 ~ 9 의 개수 : (10 ^ (k - 1)) * ( 영역 마지막 숫자 / 10 - 10 ^ (숫자 길이 - k - 1) + 1 )

 

last area

  이 영역에서 해당되는 숫자는 별로 존재하지 않으므로, 그냥 다 센다. 단 숫자 하나당 개수에 10 ^ (k - 1)을 곱해야 한다.

 

• 각 숫자 하나하나에 해당되는 정답 배열? 에 += 10 ^ (k - 1) 을 한다.

 

 <정리> 
1. 세 영역으로 나누어 계산한다.
2. 영역을 나눈 뒤 첫 째 자리 숫자, 둘 째 자리 숫자 ... 순서로 계산하게 된다.

---

  Code 

#include <iostream>
#include <cmath>
#include <string>

using namespace std;
typedef unsigned long long ull;

ull n;
ull POWER[10];
ull ans[10] = { 0, };
int p = 0;
bool isNine = false;

void printAns() { // 최종적으로 정답을 프린트
	for (int i = 0; i < 10; i++) cout << ans[i] << ' ';
}

void first_area() {
	ull p2 = p - ull(isNine? 0 : 1);			// n이 9로만 이루어진 경우가 아니면	
												//   first area 에서 숫자의 최대 길이는 p - 1 이다.
	for (int i = 0; i < p2; i++) {				// 
		for (int i = 0; i < 10; i++)
			ans[i] += POWER[p2 - 1];
		ans[0] -= POWER[i];
	}

}

void mid_area(int k) {
	n /= 10;

	for (int i = 0; i < 10; i++)
		ans[i] += (n - POWER[p - (k + 1)] + 1) * POWER[k - 1];
}

void last_area(int k) {
	while ((n % 10) != 9) {						// 첫째자리 수가 1이 될 때 까지
		string cur = to_string(n--);			//   n 값을 줄이면서
		for (int s = 0; s < cur.length(); s++)	//   줄이는 과정중의 n 값들은 하나하나
			ans[cur[s] - '0'] += POWER[k - 1];	//   숫자를 체크해서 집어넣는다.
	}
}

void init() {
	cin >> n;

	POWER[0] = 1;	// POWER array 에 대한 정의 ( POWER[k] == 10 ^ k )
	for (int i = 1; i < 10; i++) POWER[i] = POWER[i - 1] * 10;

	p = to_string(n).length();	// n의 길이(자리수)

	if (p < to_string(n + 1).length()) isNine = true;	// n에 1을 더했더니 숫자 길이가 바뀌는 경우는
}														//   n이 9로만 이루어진 숫자이다.

int main() {
	init();

	if (n < 10) { // n 이 10 미만인 경우 이 if문 안에서 끝난다.
		for (int i = n; 1 <= i; i--)
			ans[i] = 1;
		printAns();

		return 0;
	}

	int k = 1;

	first_area();

	if (!isNine) {
		for (; k <= p - 1; k++) {
			last_area(k);
			mid_area(k);
		}

		for (int i = 1; i <= n; i++)
			ans[i] += POWER[k - 1];
	}

	printAns();
}