[2021 acm-icpc] 5/22 연습 문제

1. 백준 14289번 - 본대 산책 3 (Gold 1 - 분할 정복 기법을 사용한 행렬 거듭제곱 dp 문제)

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

14289번: 본대 산책 3

 

풀이

 

결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 

 

이를 일반화 해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다.

 

이 부분을 dp스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다.

 

즉 식으로 나타내면 다음과 같다.

 

dp[i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자.

 

그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다.

 

for(int a = 1; a <= n; i++) dp[i][j][k] += dp[i][a][k-1]*dp[a][j][1]; 

-> i 노드에서 a 노드까지 k-1번 만에 가는 경우의 수 * a 노드에서 j 노드를 갈 수 있는지(0 or 1)

 

(이해를 돕기 위해 설명해보면 k번 만에 도착하려면 k-1번 째에는 반드시 도착 노드 j와 연결되어있는 다른 노드에 있어야 한다. 이를 단순하게 점화식으로 표현한 것이다.)

 

여기까지는 충분히 떠올릴 수 있었을 것이다.

 

문제는 이제부터이다.

 

k의 제한은 결국 d의 제한과 같기 때문에 1,000,000,000, 즉 10억의 제한이 걸려있다.

이뜻은 O(k)로는 해결하지 못한다는 의미였다.

 

이 부분에서 대부분(일단 나 포함ㅎ) 막혔을 것이다.

 

그럼 어떻게 해결해야 할까?

여기서 행렬의 거듭제곱이 사용된다.

 

눈치챈 천재들도 있겠지만

for(int a = 1; a <= n; i++) dp[i][j][k] += dp[i][a][k-1]*dp[a][j][1]

위 식을 행렬로 표현해보면 다음과 같다.

 

i = 1, j = 2, k = 2, n = 4라 가정해보자.

 

가정대로 위의 for문을 실행해보면 다음과 같다

둘 다 k=1이기 때문에 결국 같은 행렬에서 연산을 진행하는데 색깔별로 곱해져서 더해진다.

 

이 부분에서 행렬의 곱셈을 사용하는 걸 확인할 수 있다. (다른 항들도 마찬가지이다. 궁금하면 직접 해보길)

 

결국 k = 2 일 때의 dp 테이블은 k=1일 때의 dp 테이블을 제곱한 테이블이 되고

k = 3 일 때는 k = 2일 때의 dp 테이블 * k = 1일 때의 dp 테이블이므로 k=1일 때의 dp 테이블의 세제곱이 된다.

 

따라서 결론적으로 k = d일 때의 dp 테이블을 k = 1일 때의 dp테이블의 d제곱을 한 테이블이다.

 

여기서 dp 테이블은 그럼 어떻게 구하는가?

 

바로 노드끼리의 간선을 나타낸 인접 행렬이 k = 1 일 때의 dp 테이블이 된다.

 

우리가 구해야 했던 건 정보대에서 정보대로 k번 만에 도착하는 경우의 수이고 정보대는 1번 노드라고 문제에서 알려줬기 때문에 

 

결론적으로 우리는 "인접 행렬을 d 제곱한 행렬의 [1][1]의 값"을 구하면 된다.

 

행렬의 거듭제곱은 분할 정복 기법을 사용하여 log 시간 안에 구할 수 있기 때문에 시간 복잡도도 만족한다.

 

소스 코드(.cpp)

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

ll arr[51][51] = {};
ll rem[51][51] = {}; // 고정
ll temp[51][51] = {};
ll n, m, a, b, d;

void squared(ll a[][51], ll b[][51]) {
	memset(temp, 0, sizeof(temp));
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			for (ll k = 0; k < n; k++) {
				temp[i][j] += a[i][k] * b[k][j];
				temp[i][j] %= 1000000007;
			}
		}
	}
	memcpy(arr, temp, sizeof(arr));
}

void reculs(ll x) {
	if (x == 1) return;
	if (x % 2 == 1) {
		reculs(x / 2);
		squared(arr, arr);
		squared(arr, rem);
	}
	else {
		reculs(x / 2);
		squared(arr, arr);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		a--; b--;
		arr[a][b] = 1; arr[b][a] = 1;
		rem[a][b] = 1; rem[b][a] = 1;
	}
	cin >> d; 
	reculs(d);
	cout << arr[0][0] << "\n";
}

 

 

2. 백준 17272번 -  리그 오브 레전설 (Large) ( Gold 1 - 분할 정복 기법을 사용한 행렬 거듭제곱 dp 문제)

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

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

 

풀이

N과 M에 대해 표를 그려보면 아래와 같습니다.

n(↓), m(→)	1	2	3	4	5
1	2	1	1	1	1
2	4	2	1	1	1
3	8	3	2	1	1
4	16	5	3	2	1
5	32	8	4	3	2

 

m = 2일 때를 보면 피보나치 함수가 진행되는 것을 확인할 수 있게 됩니다.

이를 통해 m = 1일 때와 m = 3일 때를 확인해보면 m = 1일 때는 S(n) = S(n-1) + S(n-1)이 되고, m = 3일 때는 S(n) = S(n-1) + S(n-3)이 되는 것을 생각해볼 수 있게 됩니다.

 

위 표만 보고 일반화하기엔 근거가 부족하다 싶으면 n과 m을 더 추가해보고 확인해볼 수 있습니다. 

n(↓), m(→)	1	2	3	4	5	6	7
1	2	1	1	1	1	1	1
2	4	2	1	1	1	1	1
3	8	3	2	1	1	1	1
4	16	5	3	2	1	1	1
5	32	8	4	3	2	1	1
6	64	13	6	4	3	2	1
7	128	21	9	5	4	3	2

 

이것을 통하여 S(n) = S(n-1) + S(n-m)라는 식을 도출할 수 있게 됩니다.

이것을 행렬로 표현해보면 (m = 4일 때)

 

( 0  1  0  0 )

( 0  0  1  0 )

( 0  0  0  1 )

( 1  0  0  1 )

이 됩니다.

 

이 행렬을 토대로 코드를 짜면 됩니다.

 코드에서 n과 m이 바뀌어 있으므로 코드를 볼 때 헷갈리지 않도록 주의합시다.

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 101;
ll n, m;
ll MOD = 1e9+7;
ll ans[N][N] = { 0, }, arr[N][N] = { 0, };

void mul(ll A[N][N], ll B[N][N]) {
	ll res[N][N] = { 0, };
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++) 
				res[i][j] = (res[i][j] + (A[i][k] * B[k][j])) % MOD;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			A[i][j] = res[i][j];
}

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

	cin >> m >> n;
	
	for (int i = 0; i < n; i++) ans[i][i] = 1;
	arr[n - 1][0] = 1; arr[n - 1][n - 1] = 1;
	for (int i = 0; i < n - 1; i++) arr[i][i + 1] = 1;

	while (m) {
		if (m % 2) mul(ans, arr);
		mul(arr, arr);
		m /= 2;
	}
	cout << ans[n-1][n-1];
}

 

 

 

3. 백준 13430번 - 합구하기 ( Platinum IV- 분할 정복 기법을 사용한 행렬 거듭제곱 dp 문제)

문제

 

S는 다음과 같이 정의된다.

• S(0, n) = n (모든 양의 정수 n)
• S(k, n) = S(k-1, 1) + S(k-1, 2) + ... + S(k-1, n) (모든 양의 정수 k, n)

 

k와 n이 주어졌을 때, S(k, n)을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

풀이

 

이 문제같은 경우 어떤 성질을 이용해 점화식을 도출하고 ... 라는 일련의 과정보단, 직접 써보는 것이 이해가 빠를 것이다.

 

 

직접 써보니 이런 식의 표가 나왔다.

실제로 문제의 수식대로 저기까지만 계산해도 상당히 머리아픈데, 사람은 귀찮은걸 싫어하다보니.. 저거 쓰는 과정에서도 수를 빨리 도출해내는 법을 찾게 된다. 쓰다 보면 금방 찾는 규칙인데, 규칙은 다음과 같다.

 

 

파랑색 원 안의 수는 그 수 기준 왼쪽과 위쪽 빨간색 수의 합으로 나타낼 수 있다는 점이다.

이 부분은 생각해보면 간단한데, A[n][k] = A[n][k-1] + A[n-1][k-1] + ... + A[1][k-1] 이라는 속성을 표에 표시해보면

 

 

이런식으로 나타낼 수 있고, 마지막 1은 n이 1일 때 모두 동일하므로 바꿔줄 수 있다.

 

즉, A[n][k] = A[n][k-1] + A[n-1][k]

그런데 이와 같은 경우, 문제에서 나오는 n이 최대 10억이므로 도저히 계산할 수 없는 지경에 이를 수 있다.

 

하지만 우리는 위에서 해당 유형을 몇 가지 풀어봤고, 문제 조건에서 주어지는 어떤 수의 제한이 50이라면?

좀 느낌이 다르게 느껴진다. 50 x 50 행렬은 충분히 이 유형에 쓰일 수 있기 때문이다.

 

따라서 저 공식을 k에 맞춰 다시 고쳐볼 수 있다. (불편하면 자세를 고쳐앉으세요..!)

 

 

이렇게 가로로 눕혀놓는다면, n이 아무리 크더라도, k제한은 50이기 때문에 식이 확 줄어들게 된다.

이제 행렬로 표현해볼건데, 이해를 돕기 위해 몇 가지 식만 적어본다.

 

• (3, 0) = (2, 0) + 1
• (3, 1) = (2, 1) + (2, 0) + 1
• (3, 2) = (2, 2) + (2, 1) + (2, 0) + 1
• (4, 2) = (3, 2) + (3, 1) + (3, 0) + 1
• (n, k) = (n-1, k) + ... + (n-1, 0) + 1

 

행렬로 나타내면 다음과 같다.

 

 

마지막으로 우리가 아는 행렬 거듭제곱으로 시각화한다면 다음과 같다.

 

 

소스 코드(.cpp)

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

typedef long long ll;

ll ans[55][55];
ll arr[55][55];
int k, n;

const int MOD = 1000000007;

void mul(ll A[55][55], ll B[55][55]) {
	ll ret[55][55] = { 0, };
	for (int i = 0; i < k+2; i++) {
		for (int j = 0; j < k+2; j++) {
			for (int a = 0; a < k+2; a++) {
				ret[i][j] = (ret[i][j] + (A[i][a] * B[a][j])) % MOD;
			}
		}
	}
	for (int i = 0; i < 55; i++) {
		for (int j = 0; j < 55; j++) {
			A[i][j] = ret[i][j];
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> k >> n;

	for (int i = 0; i < k + 2; i++) ans[i][i] = 1;
	for (int i = 0; i < k + 2; i++) {
		for (int j = 0; j <= i; j++) {
			arr[i][j] = 1;
		}
	}

	n--;

	while (n > 0) {
		if (n % 2 == 1) mul(ans, arr);
		mul(arr, arr);
		n /= 2;
	}
	ll sum = 0;
	for (int i = 0; i < k + 2; i++) {
		sum = (sum + ans[k + 1][i]) % MOD;
	}
	cout << sum << "\n";
	return 0;
}