백준 1908번: 곱셈 전개식

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

1908번: 곱셈 전개식

---

본문에서 나온 그대로 $N$ 차식의 길이를 구하는 문제인데, 첫 발상과 case work에서 까다로움을 느낄 수 있는 문제입니다.

 

우선 $N$ 차식의 형태를 간략하게 몇 개 항만 써보겠습니다.

 

$$ x^{N} + \left ( a_{1} + a_{2} + \cdots + a_{N} \right ) x^{N-1} + \left ( a_{1}a_{2} + a_{1}a_{3} + \cdots + a_{2}a_{3} + \cdots + a_{N-1}a_{N} \right ) x^{N-2} + \cdots + a_{1}a_{2} \cdots a_{N} $$

 

이제 위 식의 길이를 구하려 하는 순간, 함정에 빠질 수 있습니다. $N$과 $N-1$ 등의 표현이 아니라 $100$, $99$와 같은 자연수가 그 위치에 있어야 하는데, 자연수의 길이가 아니라 $N$ 같이 문자의 길이를 통하여 문자열의 길이를 구해버리면 틀리게 됩니다.

 

이때 다음과 같이 정의해보겠습니다.

 

$ \textrm{digit} \left( N \right ) $ : 자연수 $N$을 10진법으로 표기하였을 때의 자릿수

 

$ \textrm{coef} \left ( N , k \right ) $ : 위 $N$ 차식에서 $x^{k}$ 의 계수의 길이 (단, $0 \leq k < N$)

 

그렇다면 $ \sum_{i=1}^{N} \textrm{digit} \left( i \right ) + \textrm{etc} = \textrm{coef} \left ( N , N-1 \right ) $ 입니다. etc 에 해당하는 부분은 밑에서 다룰 것입니다.

 

같은 방법으로, $ \textrm{coef} \left ( N , k \right ) $ 모두 $ \sum_{i=1}^{N} \textrm{digit} \left( i \right ) $을 활용하여 쉽게 구할 수 있어보입니다.

 

$N=2$일 때, $N=3$일 때는 문제 본문에서 주어지기 때문에, $N=4$일 때의 식을 써서 관찰해보겠습니다.

 

$$ x^{4} + x^{3} \left ( a_{1} + a_{2} + a_{3} \right ) + x^{2} \left ( a_{1}a_{2} + a_{1}a_{3} + a_{1}a_{4} + a_{2}a_{3} + a_{2}a_{4} + a_{3}a_{4} \right ) $$

$$ + x \left ( a_{1}a_{2}a_{3} + a_{1}a_{2}a_{4} + a_{1}a_{3}a_{4} + a_{2}a_{3}a_{4} \right ) + a_{1}a_{2}a_{3}a_{4} $$

 

이때

 

$ \textrm{coef} \left ( 4 , 3 \right ) $ 에서는 $\sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 이 나타납니다.

$ \textrm{coef} \left ( 4 , 2 \right ) $ 에서는 $3 \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 이 나타납니다.

$ \textrm{coef} \left ( 4 , 1 \right ) $ 에서는 $3 \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 이 나타납니다.

$ \textrm{coef} \left ( 4 , 0 \right ) $ 에서는 $\sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 이 나타납니다.

 

위 관찰 내용에서 $ \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 의 계수를 $k$의 크기에 따라 나열하면 $1,3,3,1$ 을 얻습니다.

같은 관찰을 $N=3$에서 하면 $1,2,1$을 얻고, $N=5$에서 하면 $1,4,6,4,1$을 얻습니다.

즉, 다음을 알 수 있습니다.

$$ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) = \sum_{j=0}^{N-1} \binom{N-1}{j} \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + \textrm{etc} $$

 

그런데 이항계수의 성질에 따라, $ \sum_{j=0}^{N-1} \binom{N-1}{j} = 2^{N-1} $ 입니다. 다시 식을 정리하면 다음을 얻습니다.

$$ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) = 2^{N-1} \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + \textrm{etc} $$

---

 

이제 위 식에서 $ \textrm{etc} $에 대해 접근하겠습니다. $N$ 차식에서 $x^{k}$ 항의 계수의 길이를 구하는 과정에서 아래 첨자는 해결됐으므로,

 

$x^{k}$ 항의 계수의 양 옆 괄호

$x^{k}$ 항의 계수의 괄호 속 $+$ 기호

$x^{k}$ 항의 계수의 괄호 속 $a$

 

이렇게 세 가지 항목의 개수를 구하면 $ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) $ 는 끝입니다.

 

첫 째로 $x^{k}$ 항의 계수의 양 옆 괄호는 $1 \leq k < N$ 에 대해 존재하므로 $2 \left ( N-1 \right )$ 개 있습니다.

 

$x^{k}$ 항의 계수의 괄호 속 $+$ 기호는 괄호 속에 항이 몇 개 있느냐에 의존하는 값입니다.

$x^{k}$ 항의 계수의 괄호 속에는 $ \binom{N}{k} $ 개의 항이 있으므로 괄호 속 $+$ 기호는 $ \binom{N}{k} - 1 $ 개 있습니다.

 

마지막으로 $x^{k}$ 항의 계수의 괄호 속 $a$는 $+$처럼 괄호 속 항의 개수와 밀접한 연관이 있습니다.

$x^{k}$ 항의 계수의 괄호 속에는 $ \binom{N}{k} $ 개의 항이 있고 각 항은 $a$를 $N-k$개 갖고 있으므로 괄호 속 $a$ 는 $ \left ( N-k \right ) \binom{N}{k} $ 개 있습니다.

 

세 항목의 값을 summation 해주면 다음을 얻습니다.

$$ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) = 2^{N-1} \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + 2 \left ( N-1 \right ) + \sum_{i=1}^{N-1} \left ( \binom{N}{i} - 1 \right ) + \sum_{i=1}^{N} i \binom{N}{i} $$

 

이항계수 성질 중,

$$ \sum_{i=1}^{N} i \binom{N}{i} = N \times 2^{N-1} $$

이고 전 파트에서 언급했던 성질에 의해

$$ \sum_{i=1}^{N-1} \left ( \binom{N}{i} - 1 \right ) = - \left ( N-1 \right ) - 2 + \sum_{i=0}^{N} \binom{N}{i} = 2^{N} - N - 1 $$

입니다.

 

이렇게 얻어낸 결과를 대입하면 다음을 얻습니다.

$$ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) = 2^{N-1} \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + 2 \left ( N-1 \right ) + 2^{N} - N - 1 + N \times 2^{N-1} $$

식을 정리하면 다음과 같습니다.

$$ \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) = 2^{N-1} \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + \left ( N+2 \right ) \times 2^{N-1} + N - 3 $$

---

 

이제 전체 식의 관점에서 볼 차례입니다.

 

$x^{k}$의 위 첨자들의 길이를 합하면 $\sum_{i=1}^{N} \textrm{digit} \left ( i \right )$ 가 아니라, $ -1 + \sum_{i=1}^{N} \textrm{digit} \left ( i \right )$ 임에 유의합니다.

$x^{k}$의 $x$의 개수를 합하면 $N$ 개입니다.

전체 식의 관점에서 각 항의 사이 $+$ 기호의 개수는 $N$ 개입니다.

 

결론적으로 $N$차식의 길이 $ \textrm{len} \left ( N \right )$은 다음과 같다는 걸 알 수 있습니다.

$$ \textrm{len} \left ( N \right ) = \sum_{k=0}^{N-1} \textrm{coef} \left ( N , k \right ) + N + N - 1 + \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $$

$$ \therefore \textrm{len} \left ( N \right ) = \left ( 2^{N-1} + 1 \right ) \times \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) + \left ( N+2 \right ) \times 2^{N-1} + 3N - 4 $$

---

 

이제 $ \sum_{i=1}^{N} \textrm{digit} \left ( i \right ) $ 을 구해야 합니다. 다행히, 이 값을 구하는 코드는 잘 알려진 편으로, [BOJ1748]에서 같은 문제를 다룹니다.

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

 

[BOJ1748]의 시간 제한은 0.15초이고, 본문의 문제의 제한 시간은 2초이므로, binary exponentiation을 사용했을 때 제한 시간이 넉넉함을 알 수 있습니다.

제가 사용한 [BOJ1748] 정답 코드의 복잡도는 $O \left ( \log N \right )$ 으로, 이를 통해 구현한 1908번의 정답 코드 또한 $O \left ( \log N \right )$입니다.

 

제가 제출한 정답 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 10000

long long LengthOf1toN (long long N);
long long power_of_2_modular (long long X);

int main() {
	
	long long N;
	scanf("%lld", &N);
	
    long long temp = power_of_2_modular(N-1);
	long long ans = (LengthOf1toN(N) * (temp+1) + 3*N - 4 + (N+2)*temp) % mod;
	
	printf("%lld", ans);
	return 0;
}

long long LengthOf1toN (long long N) {
	long long ans = 0;
	long long UpperBound = 10, LowerBound = 1;
	int digit = 1;
	while(1)
	{
		if (N < UpperBound)
		{
			ans += digit * (N - LowerBound + 1);
			break;
		}
		else
		{
			ans += digit * (UpperBound - LowerBound);
		}
		UpperBound *= 10;
		LowerBound *= 10;
		digit += 1;
	}
	return ans;
}

long long power_of_2_modular (long long X) {
	long long ans = 1, base = 2;
	while(X)
	{
		if (X % 2)
		{
			ans = ans * base % mod;
		}
		base = base * base % mod;
		X /= 2;
	}
	return ans;
}

(C11, 1116KB, 0ms, 제출번호 53353351)

---

 

본문에서 사용한 이항계수의 성질의 증명은 다음 링크에서 찾을 수 있습니다.

https://blog.naver.com/PostView.naver?blogId=yh6613&logNo=221167678486&redirect=Dlog&widgetTypeCall=true&directAccess=false