백준 BOJ 문제 풀이 모음 : 그래프와 인접 행렬의 활용 220818
백준 BOJ 17272번 : 리그 오브 레전설 (Large)
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N초를 길이가 1초인 스킬과 길이가 M초인 스킬로 구성하는 방법의 수를 구하는 문제이다.
dp[N] = dp[N-1] + dp[N-M]이라는 점화식을 세울 수 있다.
그러나 Large 문제에서는 N이 10^18 이하이므로 dp로는 풀이가 불가능하다.
따라서 점화식을 행렬로 구성하여 행렬의 거듭제곱으로 답을 구해주어야 한다.
위와 같이 점화식을 만들 수 있다.
참고로 M이 100 이하이므로, 행렬의 크기는 아무리 커도 100 x 100을 넘어가지 않는다.
위의 A 행렬을 N 제곱 해주면, 곱해지는 행렬은 a_0, a_-1, ...으로 구성되는데, 정의에 의해 a_0 = 1이고 그 외에는 0이다. (상식적으로 생각해보면 된다.)
따라서 a_N은 A^N의 0행 0열 원소가 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, ex, mod = 1e9 + 7;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> ex >> N;
mat ba(N, vector<int>(N));
ba[0][0] = ba[0][N-1] = 1;
for(int i=1; i<N; i++) ba[i][i-1] = 1;
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
cout << v[0][0] << "\n";
}
참고로 이 문제의 풀이와 같은 풀이로 백준 BOJ 17271번 : 리그 오브 레전설 (Small)을 풀이할 수 있다.
백준 BOJ 19587번 : 객실 배치
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
한 층에 2호까지 있는 N층의 객실들에 대해, 위 아래 또는 1, 2호 모두에 손님이 있지 않도록 배치하는 경우의 수를 구하는 문제이다.
한 층의 객실 배치를 0, 1, 2의 세 가지로 나누어 점화식을 세워보면 위와 같이 되고, 이는 행렬로 나타낼 수 있으며 N-1 제곱을 하여 모든 원소의 합을 통해 경우의 수를 구할 수 있다.
행렬의 log 시간 거듭 제곱을 구현하여 답을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N = 3, ex, mod = 1e9 + 7;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> ex;
mat ba(N, vector<int>(N));
ba = {{1, 1, 1},
{1, 0, 1},
{1, 1, 0}};
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
ex--;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) ans = (ans + v[i][j]) % mod;
cout << ans << "\n";
}
백준 BOJ 16467번 : 병아리의 변신은 무죄
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
모든 병아리는 매일 알을 하나씩 낳고, 각 알은 K일 후에 병아리가 된다고 할 때, N일 후 병아리의 수를 구하는 문제이다.
점화식을 세워보면 dp[i] = dp[i-1] + dp[i-1-K]이다. (dp[0] = 1, dp[i] (i < 0) = 0)
이제 나머지는 위의 백준 BOJ 17272번 문제와 똑같이 풀어주면 된다.
주의할 점은 mod 값이 1e9 + 7이 아닌 1e8 + 7이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, ex, mod = 1e8 + 7;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
cin >> N >> ex;
N++;
mat ba(N, vector<int>(N));
ba[0][0]++;
ba[0][N-1]++;
for(int i=1; i<N; i++) ba[i][i-1]++;
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
cout << v[0][0] << "\n";
}
}
백준 BOJ 23819번 : 묻고 더블로 마셔
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
1~k번째 사람이 각자 마실 양이 주어지고, k+1번째부터 N번째 사람까지는 i-1, i-2, ..., i-k번째 사람이 마신 양을 합친 것을 P로 나눈 값을 마신다고 할 때 N번째 사람이 마시는 양을 구하는 문제이다.
맨 위에서 풀이한 문제와 비슷한 방식으로 풀이할 수 있다.
이 문제는 심지어 a_1 ~ a_k 값을 모두 주기 때문에 예외 처리가 어렵지 않다.
백준 BOJ 2099번 : The game of death
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N명이 각자 2명의 사람을 지목하고, a번째 사람에서 시작해서 가리키는 사람을 K번 따라갔을 때 b번째 사람으로 도달하는 경우가 있는지를 판별하는 쿼리를 M개 처리하는 문제이다.
인접 행렬을 이용하여 풀이할 수 있다.
예를 들어 a번 사람이 b번 사람을 가리킨다면, ba[a][b] = 1로 설정한다.
그 다음 이 행렬을 K번 거듭제곱 해주면 된다.
이 때 수가 매우 커질 수 있으므로 값을 더해주지는 말고 0보다 큰 경우는 1로 처리해준다.
K번 거듭제곱 이후 ba[a][b] = 1이면 a에서 K번 이동하여 b로 이동이 가능한 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, M, K, ex;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++)
if(v[i][k] == 1 && u[k][j] == 1) w[i][j] = 1;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> K >> M;
mat ba(N, vector<int>(N));
for(int i=0; i<N; i++) {
int a, b; cin >> a >> b;
ba[i][a-1] = ba[i][b-1] = 1;
}
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
ex = K;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
while(M--) {
int a, b; cin >> a >> b;
if(v[a-1][b-1] > 0) cout << "death\n";
else cout << "life\n";
}
}
백준 BOJ 11767번 : Squawk Virus
문제 난이도 : Gold I
알고리즘 분류 : 그래프 이론, 분할 정복을 이용한 거듭제곱
그래프가 주어지고, 바이러스가 처음에 K번 노드에 1개 생성되며 바이러스 1개는 1초마다 인접한 칸들로 모두 복사된다고 할 때, t초 후 총 바이러스의 개수를 구하는 문제이다.
K번 노드에서 t번 이동을 거쳐 도달할 수 있는 모든 경로의 수를 구해주면 된다.
위의 문제와 비슷하게 인접 행렬 세팅을 하여 t번 거듭제곱 해준 뒤, v[K][i]들의 합을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, M, K, ex;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++) w[i][j] += v[i][k] * u[k][j];
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M >> K >> ex;
mat ba(N, vector<int>(N));
while(M--) {
int a, b; cin >> a >> b;
ba[a][b] = ba[b][a] = 1;
}
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
int ans = 0;
for(int i=0; i<N; i++) ans += v[K][i];
cout << ans << "\n";
}
백준 BOJ 12916번 : K-Path
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N x N 크기의 인접 행렬이 주어질 때, 길이가 M인 경로의 개수를 구하는 문제이다.
인접 행렬을 M번 거듭제곱하여 나타나는 모든 원소의 합을 구해주면 된다.
원리는 위의 문제들과 동일하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int N, ex, mod = 1e9 + 7;
mat f(mat& v, mat& u) {
mat w(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k=0; k<N; k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> ex;
mat ba(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> ba[i][j];
mat v(N, vector<int>(N));
for(int i=0; i<N; i++) v[i][i] = 1;
while(ex > 0) {
if(ex % 2 == 1) v = f(v, ba);
ba = f(ba, ba);
ex /= 2;
}
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) ans = (ans + v[i][j]) % mod;
cout << ans << "\n";
}
백준 BOJ 24731번 : XOR-ABC
문제 난이도 : Gold I
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
N자리 이진수 a, b, c에 대해 1 ≤ a < b < c ≤ 2^N - 1이고 A ^ B = C인 (A, B, C) 순서쌍의 개수를 구하는 문제이다.
내키는 방법은 아니지만 정 풀이가 어려우면 완전 탐색으로 작은 N 이하에 대해 수열을 구해보고, 규칙을 찾는 방법이 있다.
코드를 돌려보면 0, 1, 7, 35, 155, ...의 수열이 얻어진다.
규칙을 직접 찾아도 되고 OEIS를 이용해도 되는데, 아무튼 f(N) = (2^n - 1) x (2^(n-1) - 1) / 3이다.
이를 분할 정복을 이용한 거듭제곱과 페르마의 소정리를 이용해서 풀어주면 된다.
정석적인 풀이는 잘 모르겠는데, 다시 풀게 되면 정리하겠다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int a = 1, ba = 2, ex = N, mod = 1e6 + 3;
while(ex > 0) {
if(ex % 2 == 1) a = (a * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
int b = 1; ba = 2, ex = N-1;
while(ex > 0) {
if(ex % 2 == 1) b = (b * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
int ans = ((a - 1) * (b - 1)) % mod;
ba = 3, ex = mod - 2;
while(ex > 0) {
if(ex % 2 == 1) ans = (ans * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
cout << ans << "\n";
}
백준 BOJ 11440번 : 피보나치 수의 제곱의 합
문제 난이도 : Platinum V
알고리즘 분류 : 분할 정복을 이용한 거듭제곱
주어진 N에 대해 0번째 피보나치 수부터 N번째 피보나치 수의 합을 구하는 문제이다.
이 때 N은 10^18 이하이다.
10^18 이하인 N에 대해 N번째 피보나치 수는 O(log N) 시간에 구할 수 있지만, 피보나치 수의 제곱의 합을 구하기 위해 각 항을 일일이 구하게 되면 N log N 시간이 걸려 당연히 시간 초과이다.
따라서 수열을 가지고 규칙성을 찾아보자.
아래의 코드를 돌려 N = 10 이하에서의 수열을 확인해보자. (정답 코드 아님)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N+1);
v[1] = 1;
for(int i=2; i<=N; i++) v[i] = v[i-1] + v[i-2];
int sum = 0;
for(int i=1; i<=N; i++) {
sum += v[i] * v[i];
cout << i << " : " << sum << "\n";
}
}
실행시켜보면 결과는 다음과 같다.
규칙을 찾아보면, i번째 피보나치 수를 g(i)라고 했을 때 f(N) = g(N) x g(N+1)임을 확인할 수 있다.
따라서 두 피보나치 수를 분할 정복을 이용한 거듭제곱으로 구해서 곱해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int>> mat;
int mod = 1e9 + 7;
mat f(mat& v, mat& u) {
int N = 2;
mat w(N, vector<int>(N));
for(int i=0; i<v.size(); i++)
for(int j=0; j<u[0].size(); j++)
for(int k=0; k<v[0].size(); k++)
w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;
return w;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int M; cin >> M;
vector<int> v(2);
for(int t=0; t<2; t++) {
int N = M + t;
mat mul(2, vector<int>(2));
for(int i=0; i<2; i++) mul[i][i] = 1;
mat ba(2, vector<int>(2));
ba = {{1, 1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1) mul = f(mul, ba);
ba = f(ba, ba);
N /= 2;
}
v[t] = mul[0][1];
}
int ans = (v[0] * v[1]) % mod;
cout << ans << "\n";
}