UCPC 2022 예선 D-13 문제풀이 일지

목차

1. 오늘의 알고리즘 진도

- 2740번: 행렬 곱셈

- 10830번: 행렬 제곱

- 11444번: 피보나치 수 6

- 1655번: 가운데를 말해요

- 16500번: 문자열 판별

- 11066번: 파일 합치기

- 11049번: 행렬 곱셈 순서

---

오늘의 알고리즘 진도

오늘은 '단계별로 풀어보기'에 포함된 분할 정복 3문제와 우선순위 큐 1문제를 풀고 나서, 조금 어려운 다이나믹 프로그래밍 문제들에 도전해 보기로 했습니다.

C++ 템플릿 코드

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()

2740번: 행렬 곱셈

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

2740번: 행렬 곱셈

기본적인 행렬의 곱셈을 O(n^3)시간에 구하는 문제입니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M));
    forn(i, 0, N-1) forn(j, 0, M-1) cin >> A[i][j];
    cin >> M >> K;
    vector<vector<int>> B(M, vector<int>(K));
    forn(i, 0, M-1) forn(j, 0, K-1) cin >> B[i][j];
    forn(i, 0, N-1) {
        forn(j, 0, K-1) {
            int C = 0;
            forn(k, 0, M-1) {
                C += A[i][k] * B[k][j];
            }
            cout << C << " ";
        }
        cout << "\n";
    }

    return 0;
}

알고리즘 태그: 수학, 구현, 선형대수학

현 시점 난이도: 실버 V

10830번: 행렬 제곱

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

10830번: 행렬 제곱

분할 정복을 이용한 빠른 제곱을 앞서 푼 행렬 곱셈과 연결지어 푸는 문제입니다.

방식은 거의 똑같고 0제곱을 해야 할 때 단위행렬을 리턴하는 부분을 조심하면 될 것 같습니다.

int N;

vector<vector<int>> mult(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> C(N, vector<int>(N));
    forn(i, 0, N-1) forn(j, 0, N-1) forn(k, 0, N-1) {
        C[i][j] += A[i][k] * B[k][j];
        C[i][j] %= 1000;
    }
    return C;
}

vector<vector<int>> power(vector<vector<int>>& A, ll B) {
    if (B == 0) {
        vector<vector<int>> I(N, vector<int>(N));
        forn(i, 0, N-1) I[i][i] = 1;
        return I;
    }
    vector<vector<int>> U = power(A, B/2);
    U = mult(U, U);
    if (B % 2) U = mult(U, A);
    return U;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll B;
    cin >> N >> B;
    vector<vector<int>> A(N, vector<int>(N));
    forn(i, 0, N-1) forn(j, 0, N-1) cin >> A[i][j];
    vector<vector<int>> AB = power(A, B);
    forn(i, 0, N-1) {
        forn(j, 0, N-1) cout << AB[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

알고리즘 태그: 수학, 분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학

현 시점 난이도: 골드 IV

11444번: 피보나치 수 6

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

11444번: 피보나치 수 6

\(\begin{pmatrix} f(N) \\ f(N+1) \end{pmatrix}= \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^N \begin{pmatrix} 0 \\ 1 \end{pmatrix}\)의 공식을 사용하면 피보나치 수의 값을 O(logn) 시간에 계산할 수 있습니다.

vector<vector<ll>> mult(vector<vector<ll>>& A, vector<vector<ll>>& B) {
    vector<vector<ll>> C(2, vector<ll>(2));
    forn(i, 0, 1) forn(j, 0, 1) forn(k, 0, 1) {
        C[i][j] += A[i][k] * B[k][j];
        C[i][j] %= (ll)1e9 + 7;
    }
    return C;
}

vector<vector<ll>> power(vector<vector<ll>>& A, ll B) {
    if (B == 0) {
        vector<vector<ll>> I(2, vector<ll>(2));
        forn(i, 0, 1) I[i][i] = 1;
        return I;
    }
    vector<vector<ll>> U = power(A, B/2);
    U = mult(U, U);
    if (B % 2) U = mult(U, A);
    return U;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vector<vector<ll>> X = {{0, 1}, {1, 1}};
    vector<vector<ll>> XN = power(X, N);
    cout << XN[0][1];

    return 0;
}

알고리즘 태그: 수학, 분할 정복을 이용한 거듭제곱

현 시점 난이도: 골드 II

1655번: 가운데를 말해요

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

1655번: 가운데를 말해요

두 개의 우선순위 큐를 사용하는 문제.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    priority_queue<int> small, large;
    int middle;
    forn(i, 1, N) {
        int I;
        cin >> I;
        if (i == 1) middle = I;
        else if (i % 2) {
            if (I > middle) {
                small.push(middle);
                large.push(-I);
                middle = -large.top();
                large.pop();
            } else small.push(I);
        } else {
            if (I > middle) large.push(-I);
            else {
                large.push(-middle);
                small.push(I);
                middle = small.top();
                small.pop();
            }
        }
        cout << middle << "\n";
    }

    return 0;
}

알고리즘 태그: 자료 구조, 우선순위 큐

현 시점 난이도: 골드 II

16500번: 문자열 판별

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

16500번: 문자열 판별

DP 테이블을 어떻게 구성해야 할지 알쏭달쏭한 문제입니다. 입력이 크진 않아서 구현이 쉽습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int N;
    cin >> N;
    vector<string> A(N);
    forn(i, 0, N-1) cin >> A[i];
    int K = s.size();
    vector<bool> match(K+1);
    match[0] = true;
    forn(i, 0, K-1) {
        if (!match[i]) continue;
        forn(j, 0, N-1) {
            int sz = A[j].size();
            if (sz > K-i) continue;
            if (s.substr(i, sz) == A[j]) match[i+sz] = true;
        }
    }
    cout << (match[K] ? 1 : 0);

    return 0;
}

알고리즘 태그: 다이나믹 프로그래밍, 문자열

현 시점 난이도: 골드 V

11066번: 파일 합치기

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

11066번: 파일 합치기

쉽지 않았던 DP 문제입니다. 풀고 나니 어디가 어려운지 콕 집어서 말할 수가 없는데 그냥 어렵습니다...

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int K;
        cin >> K;
        vector<int> file(K+1), sum(K+1);
        forn(i, 1, K) {
            cin >> file[i];
            sum[i] = sum[i-1] + file[i];
        }
        vector<vector<int>> cost(K, vector<int>(K+1));
        // cost[i][j] = minimum cost of merging files j ~ j+i
        forn(i, 1, K-1) {
            forn(j, 1, K-i) {
                cost[i][j] = 1e9;
                forn(k, 0, i-1) {
                    int c = cost[k][j] + cost[i-k-1][j+k+1]
                            + sum[j+i] - sum[j-1];
                    cost[i][j] = min(c, cost[i][j]);
                }
            }
        }
        cout << cost[K-1][1] << "\n";
    }

    return 0;
}

알고리즘 태그: 다이나믹 프로그래밍

현 시점 난이도: 골드 III

11049번: 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

'파일 합치기' 문제와 매우 유사한 풀이를 가진 문제입니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pii> matrix(N);
    forn(i, 0, N-1) cin >> matrix[i].F >> matrix[i].S;
    vector<vector<ll>> cost(N, vector<ll>(N));
    // cost[i][j] = minimum cost of multiplying matrices j ~ j+i
    forn(i, 1, N-1) {
        forn(j, 0, N-i-1) {
            cost[i][j] = (1LL << 31) - 1;
            forn(k, 0, i-1) {
                ll c = cost[k][j] + cost[i-k-1][j+k+1]
                        + matrix[j].F * matrix[j+k+1].F * matrix[j+i].S;
                cost[i][j] = min(c, cost[i][j]);
            }
        }
    }
    cout << cost[N-1][0];

    return 0;
}

알고리즘 태그: 다이나믹 프로그래밍

현 시점 난이도: 골드 III

 

---

'행렬 곱셈 순서' 문제를 끝으로 solved.ac 프로필 상위 100문제를 모두 골드 이상으로 만들었습니다!

금요일쯤에 세운 목표인데 결국 월요일로 넘어가는 늦은 밤에야 달성했네요. 이제 자러 가야겠습니다. 내일도 화이팅~