백준 1529번: 동민 수열

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

1529번: 동민 수열

---

이 문제는 이전 두 포스팅과 아주 유사한 문제입니다. ( 12878번: Blocks ) ( 19587번: 객실 배치 )

 

우선, 다음 성질에 따라 4와 7로만 이루어진 수를 찾습니다.

 

금민수는 4와 7로만 이루어진 수이다.
$A\left [ i \right ]$ 는 금민수이다. $\left ( 0\leq i < L \right )$

 

주어진 숫자 $N$ 개에서 금민수들을 골라내는 것은 쉽습니다.

 

그런데, 인풋이 다음과 같이 주어지면 어떨까요?

 

44 44 44 44

 

이 경우, 오직 44로만 이루어지는 수열은 하나뿐이고, $44$ 끼리는 서로 구분할 수 없으므로 답은 1입니다.

 

그래서, 주어진 숫자 $N$ 개에서 중복을 제거한 금민수들의 집합을 구해야 합니다.

 

이렇게 구한 금민수들의 집합의 원소들로 동민 수열을 구성하는 문제입니다.

 

모든 $i$ 에 대해서 $A\left [ i \right ]=Numbers\left [ j \right ]$ 인 $j$ 가 존재한다. 

 

그런데 $L$ 이 적당히 작은 값이라면 수형도를 그리거나, 손으로 계산하여 정답을 알아낼 수 있을텐데

 

문제에서 요구하는 $L$ 의 범위는 $10^{9}$ 까지의 아주 큰 자연수입니다.

 

따라서, 적당한 점화식을 구해야 합니다.

 

한편 아래의 주어진 성질을 이용하여 이 문제에서도 state 들을 나누어 접근할 수 있습니다.

 

모든 $i$ 에 대해서 $A\left [ i \right ]$ 의 마지막 자리는 $A\left [ i+1 \right ]$ 의 첫번째 자리와 같다. $\left ( 0\leq i < L-1 \right )$

 

이제 state 들을 다음과 같이 정의하겠습니다.

 

길이가 $L$ 인 동민수열에 대하여,

 

$\left ( a \right )$ $A\left [ L \right ]$ 의 마지막 자리가 4인 경우

$\left ( b \right )$ $A\left [ L \right ]$ 의 마지막 자리가 7인 경우

 

또한 금민수들을 다음과 같이 분류하겠습니다.

 

$\left ( i \right )$ 4로 시작해서 4로 끝나는 수

$\left ( ii \right )$ 4로 시작해서 7로 끝나는 수

$\left ( iii \right )$ 7로 시작해서 4로 끝나는 수

$\left ( iv \right )$ 7로 시작해서 7로 끝나는 수

 

이제 길이가 $L$ 인 동민수열을 $L+1$의 길이를 가진 동민수열로 확장하는 방법은 다음과 같습니다.

 

$\left ( a \right )$ 에서 $\left ( i \right )$ 를 이용해 $\left ( a \right )$ 로 가는 경우

$\left ( a \right )$ 에서 $\left ( ii \right )$ 를 이용해 $\left ( b \right )$ 로 가는 경우

$\left ( b \right )$ 에서 $\left ( iii \right )$ 를 이용해 $\left ( a \right )$ 로 가는 경우

$\left ( b \right )$ 에서 $\left ( iv \right )$ 를 이용해 $\left ( b \right )$ 로 가는 경우

 

위에서 분류한 것들을 조금 더 명확하게 재정의해 보겠습니다.

 

길이가 $L$ 인 동민수열을, $A\left [ L \right ]$ 의 마지막 자리가 4가 되도록 구성하는 경우의 수 $A\left ( L \right )$

길이가 $L$ 인 동민수열을, $A\left [ L \right ]$ 의 마지막 자리가 7이 되도록 구성하는 경우의 수 $B\left ( L \right )$

 

4로 시작해서 4로 끝나는 금민수의 갯수 $cnt44$

4로 시작해서 7로 끝나는 금민수의 갯수 $cnt47$

7로 시작해서 4로 끝나는 금민수의 갯수 $cnt74$

7로 시작해서 7로 끝나는 금민수의 갯수 $cnt77$

 

그러면 다음 행렬 점화식을 얻을 수 있습니다.

 

$\begin{bmatrix} A\left ( L+1 \right ) \\ B\left ( L+1 \right ) \end{bmatrix}$ $=$ $\begin{bmatrix} cnt44 & cnt74 \\ cnt47 & cnt77 \end{bmatrix}$ $\begin{bmatrix} A\left ( L \right ) \\ B\left ( L \right ) \end{bmatrix}$

 

최종적인 식은 다음과 같습니다.

 

$\begin{bmatrix} A\left ( L \right ) \\ B\left ( L \right ) \end{bmatrix}$ $=$ $\begin{bmatrix} cnt44 & cnt74 \\ cnt47 & cnt77 \end{bmatrix}^{L-1}$ $\begin{bmatrix} A\left ( 1 \right ) \\ B\left ( 1 \right ) \end{bmatrix}$

 

정의에 따라 $A\left ( 1 \right )=cnt44+cnt74$ 이고, $B\left ( 1 \right )=cnt47+cnt77$ 입니다.

 

이에 따라 구현한 코드는 다음과 같습니다.

 

#include <stdio.h>
#include <stdbool.h>
#define mod 1234567891ll

int number44[50];
int number47[50];
int number74[50];
int number77[50];

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix Base, int power);

int main() {
	int N, L;
	scanf("%d %d", &N, &L);
	
	long long count44 = 0, count47 = 0, count74 = 0, count77 = 0;
	while(N--) {
		int number;
		scanf("%d", &number);
		
		int temp = number;
		int first = temp, last = temp % 10;
		
		bool flag_not_4_7 = false;
		while(first > 10) {
			if (first % 10 != 4 && first % 10 != 7) {
				flag_not_4_7 = true;
				break;
			}
			first/= 10;
		}
		if (first != 4 && first != 7) {
			flag_not_4_7 = true;
		}
		if (flag_not_4_7) {
			continue;
		}
		
		bool flag_existed_number = false;
		if (first == 4) {
			if (last == 4) {
				for (int i = 0; i < count44; i++) {
					if (number == number44[i]) {
						flag_existed_number = true;
						break;
					}
				}
				if (!flag_existed_number) {
					number44[count44] = number;
					count44 += 1;
				}
			}
			else {
				for (int i = 0; i < count47; i++) {
					if (number == number47[i]) {
						flag_existed_number = true;
						break;
					}
				}
				if (!flag_existed_number) {
					number47[count47] = number;
					count47 += 1;
				}
			}
		}
		else {
			if (last == 4) {
				for (int i = 0; i < count74; i++) {
					if (number == number74[i]) {
						flag_existed_number = true;
						break;
					}
				}
				if (!flag_existed_number) {
					number74[count74] = number;
					count74 += 1;
				}
			}
			else {
				for (int i = 0; i < count77; i++) {
					if (number == number77[i]) {
						flag_existed_number = true;
						break;
					}
				}
				if (!flag_existed_number) {
					number77[count77] = number;
					count77 += 1;
				}
			}
		}
	}
	
	Matrix Base = 
	{ 
	{
		{count44, count74},
		{count47, count77}
	}
	};
	
	Matrix Answer = 
	{
	{
		{count44 + count74, 0},
		{count47 + count77, 0}
	}
	};
	
	Base = matrix_power_modular (Base, L-1);
	Answer = matrix_multiply_modular (Base, Answer);
	
	long long answer = (Answer.array[0][0] + Answer.array[1][0]) % mod;
	printf("%lld", answer);
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result = {{{0}}};
	for (int i = 0; i < 2; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 2; j++) {
				long long temp = (A.array[i][k] * B.array[k][j]) % mod;
				result.array[i][j] = (result.array[i][j] + temp) % mod;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix Base, int power) {
	Matrix result = {{{0}}};
	result.array[0][0] = result.array[1][1] = 1;
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, Base);
		}
		Base = matrix_multiply_modular (Base, Base);
		power /= 2;
	}
	return result;
}

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

---

$cnt44\sim cnt77$ 을 구하는 과정을 조금 더럽게 짜지 않았나 싶습니다.

 

그렇지만 점화식을 구하는 건 쉬운 편입니다. 조만간 골드로 떨어지지 않을까 싶네요.