[C++/1019] 책 페이지

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

플레문제는 거들떠도 안봅니다. 그 이유는 어렵기 때문입니다. 하지만 어느순간 그런 생각이 들었습니다. 언제까지 골드만 풀래 한단계 전진해봐야지. 그렇습니다. 플레문제를 해결했습니다. 무려 4시간만에..

문제를 해결하면서 이렇게 저렇게 어떠한 규칙이 있지 않을까 어떻게 해결할까 고민을 많이 했습니다. 아주 오랜만에, 대부분의 골드나 실버 문제는 특별한 알고리즘이 아닌 구현에 치중해서 문제를 해결했었는데, 이 문제는 수학적이라고 해야할지 문제를 천천히 쪼개면서 해결했습니다.

9000번까지 가려면 1~9까지를 몇번을 반복해야할까요? 처음부터 9000이라는 큰 숫자를 맞이하기 때문에 굉장히 부담스럽습니다. 그렇다면 14는 어떨까요? 14까지가려면 1~9를 한번 그리고 0~4까지 한번을 가야합니다. 즉, 1~4는 두번 0은 1번 나머지 5~9까지는 한번입니다. 여기서 문제 힌트를 얻었습니다.

계속해서 숫자를 써내려가면서 문제를 파악할 수 있었습니다. 그럼 세가지의 경우의 수가 나오고 마지막 하나를 남겨두고 있습니다. 무엇이냐면 두번 반복되는 1~4는 일의 자리수 반복이지만, 십의 자리수는 1로 연속해서 4번이 나온다는 것입니다. 이러한 내용을 구현 하면 됩니다. 정리하겠습니다.

0은 어떻게 구할 수 있을것인가? 0은 무조건 십의 자리까지 가야지 1번이 됩니다. 그렇다는 얘기는? 100까지 가는데 10번밖에 안나온다는 얘기이고, 이러한 규칙을 찾아내야합니다. 

제가 찾아낸 규칙은 1의 자리를 파악할 때는 0부터 해당 숫자(일의 자리) 전까지 포함해 1번을 더해주지만, 0은 현재 자리수 만큼 제외를 해줍니다. 

1의 자리지만 10의 자리까지 0~9가 몇번 생성되냐를 따지는 것이기 때문에 1만큼 빼줍니다.

10의자리지만 100의자리까지 0~9가 몇번 생성되냐를 따지는 것이기 때문에 10의 자리값인 10 만큼 빼줍니다.

100의자리지만 1000의 자리까지 0~9가 몇번 생성되냐를 따지는 것이디 때문에 100의 자리 값인 100만큼 제외를 합니다.

그렇게 0의 개수를 구할 수 있습니다. 이 내용을 글로 작성하려하니 어려운데, 그림을 그려서 생각하면 쉽게 떠올릴 수 있을 것 같습니다.

14를 예시로 1~9 한번, 0~4 한번 이되고, 10의 자리수 1은 4번 더 반복해서 나오게 됩니다. 이 내용을 토대로 작성한 코드입니다. 추후 좀 더 가독성있게 작성해야될 것 같습니다.

#include<iostream>

using namespace std;

int n,count[11],add=0;

/*
10의 자리는 10을 나눈 값만큼
100의 자리는 100을 나눈 값만큼
1000의 자리는 1000을 나눈 값만큼
10000의 자리는 10000을 나눈 값만큼
*/

int main() {
	
	cin >> n;
	
	for(int i = 1; n != 0; i *= 10){ // 1의 자리, 10의 자리, 100의 자리 각 도는 횟수가 다름 
		
		int number = n % 10;
		n /= 10;
		
		count[0] -= i;
		
		for(int j = 0; j < number; j++){
			count[j] += (n + 1) * i;
		} // 0 ~ 9 가 몇번 돌았을까? 
		
		count[number] += n * i + 1 + add; // 이전 앞서있던 제자리 값은 몇번 돌았을까? 
		
		for(int j = number + 1; j <= 9; j++){
			count[j] += n * i; // 이후의 값은 몇번 돌았을까? 
		}
		
		add += number * i; // 그 나머지 숫자만큼 i번 돌았겠지? 
		
	}
	
	for(int i = 0; i <= 9; i++){
		cout << count[i] << " ";
	} 
	
	return 0;
}