[백준] 1019번: 책 페이지 C++로 풀어보기

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

1019번: 책 페이지

 

1019번 설명

생각

페이지를 단순히 읽어나가면서 계산하면 당연히 시간초과가 발생한다.

 

하지만 아무리 생각해도 내 실력으로는 해결할 수가 없었다. 따라서 밑의 블로그 내용을 참고했다.

(그림도 그려가면서 상세히 설명해주셔서 더욱 이해하기에 편리했다.)

https://restudycafe.tistory.com/489

[백준/BOJ] 1019번 : 책 페이지 (수학, Counting) (+ Class 6 획득)

 

메인 아이디어는 일의 자리부터 시작해서

현재 자리의 수보다 작은 수들은 (n / 10 + 1) * (현재 자리 수),

현재 자리의 수는 add라는 변수를 사용하여 따로 계산,

현재 자리의 수보다 큰 수들은 (n / 10) * (현재 자리 수)로 계산한다는 것이다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[10];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	int add = 0; // 현재 자릿수에 해당하는 숫자를 계산하기 위해 만든 변수
	cin >> n;

	for (int i = 1; n != 0; i *= 10) {
		int now = n % 10; // n을 10으로 나눈 나머지
		n /= 10; // n을 10으로 나누어준다.

		arr[0] = arr[0] - i; // 처음에 계산할 때 0은 포함되지 않으므로 빼준다.
		// ex) 처음에 수가 0,1,2,3,4,5,6,7.... 이 때 0은 빼줘야 되니까


		// 현재 자릿수에 해당하는 숫자보다 작은 수들
		// 일의 자리를 계산한다고 가정해보자.
		// 만약 숫자가 123이라면 0,1,2는 120, 121, 122로 다른 숫자들보다 한 번 더 세어줘야한다.
		for (int j = 0; j < now; j++) { 
			arr[j] += (n + 1) * i;
		}

		// 현재 자릿수에 해당하는 숫자
		// 십의 자리를 계산한다고 가정해보자.
		// 만약 숫자가 123이라면 2는 120, 121, 122, 123 총 4번 나오므로
		// 다른 숫자와는 다르게 계산해줘야 함을 알 수 있다.
		arr[now] += n * i + 1 + add;

		// 현재 자릿수에 해당하는 숫자보다 큰 수들
		for (int j = now + 1; j <= 9; j++) {
			arr[j] += n * i;
		}

		add += now * i;
	}

	for (int i = 0; i < 10; i++) { // 출력
		cout << arr[i] << " ";
	}
}

n = 123이라고 해보자

1. 일의 자리
now는 3이고 n은 12가 된다.

arr[0]은 1이 빼진다.

arr[0] = (12+1) * 1;
arr[1] = (12+1) * 1;
arr[2] = (12+1) * 1;

arr[3] = 12 * 1 + 1 + 0(add);

arr[4] = 12 * 1;
arr[5] = 12 * 1;
..
arr[9] = 12 * 1;

add = add + 3 * 1;

2. 십의 자리
now는 2이고 n은 1이 된다.

arr[0]은 10이 빠진다.

arr[0] = (1 + 1) * 10;
arr[1] = (1 + 1) * 10;

arr[2] = 1 * 10 + 1 + 3 = 14

arr[3] = 1 * 10
arr[4] = 1 * 10
...
arr[9] = 1 * 10

add = add + 2 * 10

3. 백의 자리
now는 1이고 n은 0이 된다.

 

arr[0]은 100이 빠진다.

 

arr[0] = (0 + 1) * 100;

 

arr[1] = (0 * 100) + 1 + 20 = 21

 

그 뒤로는 n이 0이므로 계속 0이다.