문제를 많이 풀었는데 플래티넘 문제를 한번도 안 풀어봤다는 사실을 깨닫고,

클래스5를 달성한 김에, 클래스6에서 플래티넘 문제를 한번 풀어보려고 계획해서 선정한 문제였다.

처음 시도한 방법은 문제를 두 단계로 나누어서 생각하는 방법이였다:

배열을 하나 만들어서 dp[자릿수][수]로 정보를 보관한다.

N이 3254라면,

1. 1~9, 10~99, 100~999까지는 모든 수가 사용되었기 때문에  자릿수를 늘려가며 배열을 활용하여 값을 구한다

2. 1000~3254를 구할때 기존의 dp 배열을 활용하여 계산을 한다

2 번을 어떻게 구현할까 생각하다 1번을 적절히 활용하면 되겠다는 생각을 했다.

3254라면,

0XXX, 1XXX, 2XXX의 경우에는 000-999가 전부 쓰인셈이고

30XX, 31XX는 00-99가 전부 쓰인셈이고

320X, ~ 324X는 0-9가 전부 들어갈 수 있고,

마지막으로 3250~3254만 계산하면 될 것이다.

이런식으로 생각하는 과정에서, 특정 자릿수까지 수가 얼마나 쓰였는지 계산하는 방법은 간단하다는걸 깨달았다.

000~999에서 8이 얼마나 쓰였는지 아는 방법은 다음과 같다:

8은 백의 자리, 십의 자리, 일의 자리에 각각 들어갈 수 있으며,

그때마다 다른 두 자리에 0부터 9까지가 들어갈 수 있으니, 10^2 * 3 = 300이 된다.

1부터 9까지는 동일한데, 0은 조금 특수하게 생각해야 한다.

제일 앞 자리가 0으로 시작할 수는 없기 때문에, 나누어 생각해야 한다.

0XXX 식으로 앞에 수가 없는 경우와 앞에 1부터 9사이의 수가 있는 경우

후자의 경우에는 다른 수와 같은 방식으로 계산하면 되고, 전자의 경우에는

X0X, XX0로 앞에 들어갈 수가 없으며, 또 제일 앞자리는 0-9가 아닌 1-9로 계산해야 하며,

대신 0X0의 경우에는 0이 하나라도 들어갈 수 있다는 점도 고려해야 한다.

따라서 10^1 * 9 * 2 + 10^0 * 9 * 1 = 189가 된다

추가로, 32XX와 같이 3200-3299까지의 수를 위의 방식대로 고려할 때,

해당 범위의 수만큼 앞 32가 반복적으로 들어가기 때문에, 이 또한 계산에 포함시켜야 한다.

코드로 구현하면 다음과 같다

void calc(vector<unsigned long long>& result, vector<int> base, int length) {

	bool nobase = true;
	for (auto& digit : base) {
		if (digit > 0) {
			nobase = false;
			break;
		}
	}

	unsigned long long sum = 0;
	if (!nobase) {
		result[0] += pow(10, length - 1) * length;
	}
	else {
		for (int k = length; k >= 2; k--) {
			result[0] += pow(10, k - 2) * (k - 1) * 9;
		}
	}
	for (int i = 1; i <= 9; i++) {
		result[i] += pow(10, length - 1) * length;
	}
	for (int i = 0; i <= 9; i++) {
		if (length == 0)
			result[i] += base[i];
		else
			result[i] += base[i] * pow(10, length);
	}
}

명명이 직관적이지 않은 관계로, 부연설명을 하자면

base는 해당 구간을 게산할 때 앞 자리 수의 구성을 담은 배열이다 (32XX면 3 1개, 2 1개)

따라서 해당 배열 내의 값이 모두 0이면 앞 자리가 0으로 시작한다는 뜻이므로, 그에 맞추어 0의 처리를 한다

코드 줄 수를 줄이려면 1부터 9까지 등장 횟수를 연산할 때 0부터 시작하게 바꾸면 되겠지만

0처리에 대한 부분이 분기로 나뉘어져 직관적으로 보여야 생산성 있는 코드라고 생각하기 때문에 저렇게 작성했다.

이 부분은 반복적으로 사용되기 떄문에 메모이제이션을 해 두면 반복을 조금 줄여 최적화를 할 수 있겠으나

핵심이 아니기도 하고 제한 시간내에 정상적으로 동작하기 때문에 그대로 놔두었다.

" 0XXX, 1XXX, 2XXX의 경우에는 000-999가 전부 쓰인셈이고

30XX, 31XX는 00-99가 전부 쓰인셈이고

320X, ~ 324X는 0-9가 전부 들어갈 수 있고,

마지막으로 3250~3254만 계산하면 될 것이다 " 에 대한 구현을 담은 코드는 다음과 같다

vector<unsigned long long> result(10, 0);
vector<int> base(10, 0);
for (int i = 0; i < str.length(); i++) {
    for (int j = 0; j < str[i] - '0'; j++) {
        if (i != 0 || j != 0)
            base[j] += 1;
        calc(result, base, str.length() - i - 1);
        if (i != 0 || j != 0)
            base[j] -= 1;
    }
    base[str[i] - '0'] += 1;
}

if문의 의미는 처음 시작할때 0XXX에 대해 연산하게 되는데, 이를 적절히 처리하기 위한 예외문이다.