변수가 2개 이상인 DP를 푸는 요령

변수가 2개 이상인 DP란?

Dymanic Programming에는 항상 점화식이 따라온다.
가장 간단한 DP문제인 피보나치 수열의 점화식은
$F(0) = 1, F(1) = 1$
$F(i) = F(i-1) + F(i-2), (i \geq 2)$
이다.
이런 문제는 점화식의 변수가 한 개이나, 변수가 2개 이상인 점화식을 도출해 풀 수 있는 문제도 많다.

이러한 DP 중 유명한 예로 플로이드-와샬 알고리즘이 있다.
모든 정점 쌍의 최단거리를 도출하는 알고리즘으로, 시간복잡도는 $O(N^3)$이다.

점화식은
$dp(i,j,0) = w(i,j)$
$dp(i,j,k) = min((dp(i,k,k-1) + dp(k,j,k-1)), dp(i,j,k-1))$
로 표현이 가능하다.

$dp(i,j,k)$가 의미하는 것은 정점 $0,1,...,k$를 경유하는 점으로 사용해 $i$에서 $j$로 가는 최단거리이다.

코드로 표현하면 다음과 같다.

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

void Floyd_Warshall (vector<vector<ll>> edge, int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && edge[i][k] + edge[k][j] < edge[i][j]) {
                    edge[i][j] = edge[i][k] + edge[k][j];
                }
            }
        }
    }
}

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

    int n, m;
    cin >> n >> m;
    vector<vector<ll>> edge;
    edge.resize(n, vector<ll>(n, INT_MAX));
    int s, e, cost;
    for (int i = 0; i < m; i++) {
        cin >> s >> e >> cost;
        s--; e--;
        if (edge[s][e] > cost) edge[s][e] = cost;
    }
    Floyd_Warshall(edge, n);
}

아래 문제들은 위의 플로이드-와샬과 비슷한 점화식 도출 난이도(점화식 형태도 비슷하다..), 구현 난이도를 가지는 문제들이다.
세 문제 다 $dp(i,j)$에서 $j-i$가 작은 것부터 구해나가는 것이 특징이다.

백준 11049
백준 11066
백준 10942

---

백준 11049 행렬 곱셈 순서

점화식
$dp(i,j)$ : $i$~$j$번째까지 곱하는데 필요한 곱셉 횟수
$dp(i,i) = 0 ( 0 \leq i \leq n-1)$
$dp(i,i+1) = arr[i][0] + arr[i+1][1] (0 \leq i \leq n-2)$
$dp(i,j) = min_{k=i}^{j-1}(dp(i,k)+dp(k+1,j)+dp(k,k+1)) (j-i \geq 2)$

시간복잡도는 $O(N^3)$이다.

소스코드 보기

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

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

    int n; cin >> n;
    vector<pair<int,int>> v1;
    for (int i = 0; i < n; i++) {
        int a,b; cin >> a >> b;
        v1.push_back({a,b});
    }
    int dp[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; i+j < n; j++) {
            int min = INT_MAX;
            for (int x = 0; x < i; x++) {
                int tmp = dp[j][j+x]+dp[j+x+1][i+j]+v1[j].first*v1[j+x].second*v1[i+j].second;
                if (min > tmp) min = tmp;
            }
            dp[j][i+j] = min;
        }
    }

    cout << dp[0][n-1];
}

 

백준 11066 파일 합치기

점화식
$dp(i,j)$ : $i$~$j$번째까지 합치는 비용
$dp(i,i) = 0 ( 0 \leq i \leq n-1)$
$dp(i,j) = min_{k=i}^{j}(dp(i,k)+dp(k,j)+\sum_{x=i}^j arr[x]) (j-i \geq 1)$

$\sum_{x=i}^j arr[x]$는 누적합을 이용해 구해준다.

시간복잡도는 $O(N^3)$이다.

소스코드 보기

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

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

    int tc; cin >> tc;
    for (int i = 0; i < tc; i++) {
        int n; cin >> n;
        int arr[n];
        for (int j = 0; j < n; j++) cin >> arr[j];
        int sum[n]; sum[0] = arr[0];
        for (int j = 1; j < n; j++) sum[j] = sum[j-1]+arr[j];

        int dp[n][n];
        for (int j = 0; j < n; j++) dp[j][j] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; i+j < n; j++) {
                int minval = INT_MAX;
                for (int x = 0; x < i; x++) {
                    if (minval > dp[j][j+x] + dp[j+x+1][i+j]) {
                        minval = dp[j][j+x] + dp[j+x+1][i+j];
                    }
                }
                if (j == 0) dp[j][i+j] = sum[i+j]+minval;
                else dp[j][i+j] = sum[i+j]-sum[j-1]+minval;
            }
        }
        cout << dp[0][n-1] << '\n';
    } 
}

 

백준 10942 팰린드롬?

점화식
$dp(i,j)$ : $i$~$j$ 문자열이 팰린드롬이면 1, 아니면 0
$dp(i,i) = 1 ( 0 \leq i \leq n-1)$

$dp(i,i+1)=1 (arr[i]=arr[i+1]), 0 (else)$

$dp(i,j) =1 (arr[i]=arr[j], dp(i+1,j-1)=1), 0 (else)$

시간복잡도는 $O(N^2+M)$이다.

소스코드 보기

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

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

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

    int dp[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    } 
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int i = 0; i < n-1; i++) {
        if (arr[i] == arr[i+1]) dp[i][i+1] = 1;
        else dp[i][i+1] = 0;
    }

    for (int j = 2; j < n; j++) {
        for (int i = 0; i+j < n; i++) {
            if (dp[i+1][i+j-1] == 1 && arr[i] == arr[i+j]) dp[i][i+j] = 1;
            else dp[i][i+j] = 0;
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (dp[a][b] == 1) cout << "1" << '\n';
        else cout << "0" << '\n';
    }
}