백준 17272번: 리그 오브 레전설 (Large)

www.acmicpc.net/problem/17272

17272번: 리그 오브 레전설 (Large)

---

이 문제와 비슷한 형태의 행렬 점화식이 문제에서 종종 나오는데, 난이도가 꽤 있는 유형이라고 생각합니다.

 

시간이 N일 때 가능한 스킬 조합의 수를 $A_{N}$ 이라고 해보겠습니다.

 

우선 간단한 경우를 먼저 탐색해보기 위해 $M=2$ 라고 해보겠습니다.

 

그 경우 $A_{1}=1,A_{2}=2,A_{3}=3,A_{4}=5,A_{5}=8,\cdots$ 나름대로 피보나치 수열과 비슷한 모습입니다.

 

$M=3$ 이라고 해보겠습니다.

 

그러면 $A_{1}=1,A_{2}=1,A_{3}=2,A_{4}=3,A_{5}=4,A_{6}=6,\cdots$ 규칙이 보이시나요?

 

저는 잘 안 보였습니다.

 

만약 보였다고 해도, 이 문제에선 $M$ 의 값에 의존하는 규칙은 그렇게 좋은 규칙이 아닐 것입니다.

ex) M=2일 때 피보나치와 겹치는 것, etc.

 

다시 원점으로 돌아와서 $A_{N}$의 값을 알 때 $A_{N+1}$의 값을 구할 방법이 있을까요?

 

일단, $N+1$초 동안 스킬을 쓰는 건 다음의 두 가지 경우가 있겠습니다.

 

$N$초 동안 스킬을 쓴 뒤 $N$초부터 $N+1$초까지 스킬 A를 쓰는 것

 

$N+1-M$초 동안 스킬을 쓴 뒤 $N+1-M$초부터 $N+1$초까지 스킬 B를 쓰는 것

 

따라서, $A_{N+1}=A_{N}+A_{N+1-M}$ 이었습니다.

 

이 점화식은 2 이상 100 이하의 모든 $M$ 과 모든 $N\geq M$에 대해 성립하므로 좋은 점화식이라고 생각할 수 있습니다.

 

보통 이런 모양의 점화식은 행렬로 해결합니다.

 

그런데 그 모양이 잘 보이지 않을 수도 있으니, 우선 $M$의 값을 작은 것부터 대입하여 규칙성을 도출해보겠습니다.

 

$M=2$ 일 때

 

$A_{N}=A_{N-1}+A_{N-M}=A_{N-1}+A_{N-2}$

 

$A_{4}=A_{3}+A_{2}$

 

$\therefore \begin{bmatrix}A_{2}\\ A_{3}\\ A_{4}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\end{bmatrix}\begin{bmatrix}A_{1}\\ A_{2}\\ A_{3}\end{bmatrix}$

 

$A_{5}=A_{4}+A_{3}$

 

$\therefore \begin{bmatrix}A_{3}\\ A_{4}\\ A_{5}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\end{bmatrix}\begin{bmatrix}A_{2}\\ A_{3}\\ A_{4}\end{bmatrix}$

 

$\therefore \begin{bmatrix}A_{N-2}\\ A_{N-1}\\ A_{N}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\end{bmatrix} \begin{bmatrix}A_{N-3}\\ A_{N-2}\\ A_{N-1}\end{bmatrix}$

 

 

같은 방법으로 $M=3$ 일 때

 

$A_{N}=A_{N-1}+A_{N-3}$

 

$\therefore \begin{bmatrix}A_{N-3}\\ A_{N-2}\\ A_{N-1}\\ A_{N}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\end{bmatrix} \begin{bmatrix}A_{N-4}\\ A_{N-3}\\  A_{N-2}\\ A_{N-1}\end{bmatrix}$

 

이제 규칙성이 보이나요?

 

자연수 $M$ 에 대해 필요한 행렬의 크기는 $\left ( M+1 \right )\times \left ( M+1 \right )$이 될 것입니다.

 

또한 이 식이 성립할 것입니다.

 

$\begin{bmatrix}A_{N-M}\\ A_{N-M+1}\\ A_{N-M+2}\\ \vdots\\ A_{N-2}\\ A_{N-1}\\ A_{N}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 0 & 0 & 1 & 0 & \cdots & 0 & 0\\ 0 & 0 & 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1\\ 0 & 1 & 0 & 0 & \cdots & 0 & 1\end{bmatrix}\begin{bmatrix}A_{N-1-M}\\ A_{N-1-M+1}\\ A_{N-1-M+2}\\ \vdots\\ A_{N-3}\\ A_{N-2}\\ A_{N-1}\end{bmatrix}$

 

이제 이를 이용하여 잘 구현하면 끝입니다.

 

이때 다음이 $M$ 에 관계없이 항상 성립함을 쉽게 알 수 있습니다.

 

$1\leq i \leq M-1$ 일 때 $A_{i}=1$

 

$A_{M}=2$

 

$A_{M+1}=3$

 

최종 시간복잡도는 $O\left ( M^{3}logN \right )$이 되겠습니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000007

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

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

int main() {
	
	long long N;
	int M;
	scanf("%lld %d", &N, &M);
	
	if (N < M) {
		printf("1");
	}
	else if (N == M) {
		printf("2");
	}
	else if (N == M + 1) {
		printf("3");
	}
	else {
		int size = M + 1;
		long long power = N - M - 1;
		
		Matrix Base = { {0,} };
		for (int i = 0; i < size - 1; i++) {
			Base.array[i][i+1] = 1;
		}
		Base.array[size-1][1] = Base.array[size-1][size-1] = 1;
		
		Matrix Answer = { {0,} };
		for (int i = 0; i < size - 2; i++) {
			Answer.array[i][0] = 1;
		}
		Answer.array[size-2][0] = 2, Answer.array[size-1][0] = 3;
		
		Base = matrix_power_modular (Base, size, power);
		Answer = matrix_multiply_modular (Base, Answer, size);
		
		printf("%lld", Answer.array[size-1][0]);
	}
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix Result = { {0,} };
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; k++) {
				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 size, long long power) {
	Matrix Result = { {0,} };
	for (int i = 0; i < size; i++) {
		Result.array[i][i] = 1;
	}
	while(power) {
		if (power % 2) {
			Result = matrix_multiply_modular (Result, Base, size);
		}
		Base = matrix_multiply_modular (Base, Base, size);
		power /= 2;
	}
	return Result;
}

 

(C11, 1712KB, 460ms, 제출번호 26473172)

---

코드 길이 좀 줄여보려고 구조체 초기화를 좀 했는데, 그냥 memset을 쓰는 게 나았을 수도 있겠다 싶습니다.

 

백준에서 경고가 뜨네요.

 

$M=3$일 때 규칙을 쉽게 찾았다면, $M$ 의 값을 늘려가면서 $A_{N}=A_{N-1}+A_{N-M}$을 쉽게 유도할 수 있었을 것입니다.

 

$1\leq i\leq M-1$ 일 때 $A_{i}=1$ 인 것은 가능한 스킬 조합이 A, AA, AAA, $\cdots$, 밖에 없기 때문입니다.

 

$A_{M}=2$ 인 것은 $AAA\cdots AAA$ 또는 $B$ 밖에 없기 때문입니다.

 

$A_{M+1}=3$ 는 $BA$ 나 $AB$ , 또는 $AAA\cdots AAA$ 밖에 없기 때문입니다.

 

---

구조체 초기화와 locality에 관하여 코드 수정을 했습니다.

 

수정된 코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000007

typedef struct {
	unsigned long long array[101][101];
} Matrix;

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

int main() {
	
	long long N;
	int M;
	scanf("%lld %d", &N, &M);
	
	if (N < M) {
		printf("1");
        return 0;
	}
	
    if (N == M) {
		printf("2");
	    return 0;
    }
	
    if (N == M + 1) {
	    printf("3");
	    return 0;
    }
    
	int size = M + 1;
	long long power = N - M - 1;
		
	Matrix Base = { {{0}} };
	for (int i = 0; i < size - 1; i++) {
		Base.array[i][i+1] = 1ULL;
	}
	Base.array[size-1][1] = Base.array[size-1][size-1] = 1;
	
	Base = matrix_power_modular (Base, size, power);
        
    unsigned long long Answer = 0;
    for (int i = 0; i < size - 2; i++) {
        Answer = (Answer + Base.array[size-1][i]) % mod;
    }
    Answer = (Answer + Base.array[size-1][size-2] * 2) % mod;
	Answer = (Answer + Base.array[size-1][size-1] * 3) % mod;
        
	printf("%llu", Answer);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix Result = { {{0}} };
	for (int i = 0; i < size; i++) {
		for (int k = 0; k < size; k++) {
			for (int j = 0; j < size; j++) {
				unsigned 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 size, long long power) {
	Matrix Result = { {{0}} };
	for (int i = 0; i < size; i++) {
		Result.array[i][i] = 1;
	}
	while(power) {
		if (power % 2) {
			Result = matrix_multiply_modular (Result, Base, size);
		}
		Base = matrix_multiply_modular (Base, Base, size);
		power /= 2;
	}
	return Result;
}

(C11, 1632KB, 244ms, 제출번호 28022545)

---