[Baekjoon] 1019번: 책 페이지

 

 

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

1019번: 책 페이지

 

---

 

문제 해결 과정

착안

각 자릿수마다 숫자 0부터 9까지 등장하는 규칙성을 찾아 이를 이용해 계산한다.

 

책의 마지막 페이지가 5425 페이지라고 가정하여 아래와 같이 규칙성을 파악해보자.

위의 그림과 같이 1부터 5425까지 모든 숫자를 자릿수 별로 확인하기 편하게 나열해보면,

• 일의 자리가 0인 숫자: 0, 10, 20, $\cdots$, 5420 $\Rightarrow$ (543 - 1) 개 (첫 페이지가 1부터 시작하므로)
• 일의 자리가 1인 숫자: 1, 11, 21, $\cdots$, 5421 $\Rightarrow$ 543 개
• 일의 자리가 2, 3, 4인 숫자: 1인 경우와 마찬가지로, 각각 543 개
• 일의 자리가 5인 숫자: 542 + 1개
• 일의 자리가 6, 7, 8, 9인 숫자: 각각 542 개

임을 쉽게 확인해볼 수 있다. 이때, 5425를 10으로 나눈 몫(quotient)인 542가 반복적으로 사용되는 점과, 마지막 페이지의 일의 자릿수인 5로 끝나는 숫자의 갯수 계산에 유의하며 다음 단계를 수행하여 규칙성을 찾아보자.

 

 

십의 자리에 등장하는 숫자를 카운팅할 때는 일의 자리 숫자를 x로 표현해 묶음으로 갯수를 파악하는 것이 용이하다.

각각의 숫자 묶음이 숫자 10 개씩을 의미하는 것에 유의해야 한다

 

• 십의 자리가 0인 숫자: (54 + 1) 묶음에서 0으로 시작하는 숫자는 없으므로 한 묶음을 제외하면, 540 개
• 십의 자리가 1인 숫자: (54 + 1) 묶음이므로 550 개
• 십의 자리가 2인 숫자: 542x에 포함되는 숫자는 5420 ~ 5425 뿐이므로, 54 묶음 + (5 + 1) 개 = 546 개
• 십의 자리가 3, 4, $\cdots$, 9인 숫자: 54 묶음이므로, 각각 540 개

 

각각의 숫자 묶음이 숫자 100 개씩을 의미하는 것에 유의해야 한다

 

이러한 과정을 반복하다보면 아래와 같이 귀납적으로 추론해볼 수 있다.

 

1부터 $N$ 까지 일의 자리, 십의 자리, ... 마다 나타나는 각각의 숫자의 갯수를 계산할 때,

• 일의 자리, 십의 자리, $\cdots$ 의 숫자가 $N$과 다른 경우: $N$을 10, 100, $\cdots$ 로 나눈 몫을 이용해 계산.
• 일의 자리, 십의 자리, $\cdots$ 의 숫자가 $N$과 같은 경우: $N$을 1, 10, $\cdots$ 로 나눈 몫과 나머지를 이용해 계산.

 

구현

위에서 찾아낸 규칙성을 각 자리마다 반복적으로 적용하면 문제를 해결할 수 있다.

 

편의상, 0부터 9까지 각각 10 개의 숫자들이 등장하는 갯수를 누적하여 저장할 배열을 Nums[] 라고 하고, 책의 마지막 페이지 $N$이 $k$ 자리의 숫자라고 할 때, 반복문을 통해 1부터 $N$ 까지 숫자들을 1, 10, 100, $\cdots$ 개씩 묶으며 ($up$이라는 변수로 제어) 각 자리마다 다음과 같이 반복 계산하여 문제를 해결할 수 있다.

• 숫자 $N$의 일의 자리 숫자 $r$를 구한다.
• 숫자 $N$을 10으로 나눈 몫($q$)을 저장한다.
• Nums[$i$] 배열의 요소들을 아래와 같이 갱신한다.
  1. $0 \le i \le r - 1$ 인 경우: Nums[$i$] += ($q$ + 1) $\times \space up$;
  2. 앞의 숫자가 0으로 시작하는 경우 제외: Nums[0] -= $up$;
  3. $i = r$ 인 경우: Nums[$i$] += $q \times up$ + ($N$ % $up$ + 1);
  4. $r + 1 \le i \le 9$ 인 경우: Nums[$i$] += $q \times up$;
• $N$의 값을 10으로 나눈 몫으로 갱신($N$ /= 10;) 하고 , $N > 0$ 이면 위의 과정들을 반복 수행한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Nums[10];

int main()
{
	int N;
	cin >> N;

	int n = N;
	for (int up = 1; n > 0; up *= 10)
	{
		int r = n % 10;		// 현재 단계 자리 숫자
		int q = n / 10;		// 현재 자리 보다 앞 숫자들

		int temp = q * up;
		for (int i = 0; i < r; i++)			// 1) d < r인 숫자 갯수
			Nums[i] += temp + up;
		Nums[0] -= up;						// 2) 앞자리가 0인 숫자 제외

		Nums[r] += temp + (N % up + 1);		// 3) d = r인 숫자 갯수

		for (int i = r + 1; i < 10; i++)	// 4) r < d <= 9인 숫자 갯수
			Nums[i] += temp;

		n /= 10;
	}

	for (int i : Nums)
		cout << i << " ";
	cout << "\n";
	return 0;
}

 

실행 결과