백준 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";
}