백준13260 문자열 자르기

작성일 | In

문제 링크

  • http://icpc.me/13260

사용 알고리즘

  • DP
  • Knuth optimization

시간복잡도

  • O(n2)

풀이

(이 글과 이 글을 먼저 읽어주시기 바랍니다.)

dp[i][j]를 i번째 위치부터 j번째 위치까지 자르는 비용이라고 정의합시다.
C[i][j]를 i번째 위치부터 j번째 위치까지의 길이라고 정의합시다.

dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j] 라는 점화식을 세울 수 있습니다.
C배열은 사각부등식과 단조성을 만족하기 때문에 Knuth Optimization을 적용시킬 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1000000000000000000LL;
ll d[1003][1003];
int p[1003][1003];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;

    vector<int> a(n+2);
    for (int i=1; i<=n; i++) cin >> a[i];
    a[n+1] = m;
    sort(a.begin(), a.end());
    n += 2;

    for (int i=0; i<n; i++) {
        d[i][i] = 0, p[i][i] = i;
        for (int j=i+1; j<n; j++) d[i][j] = 0, p[i][j] = i;
    }

    for (int l=2; l<=n; l++) {
        for (int i=0; i+l<n; i++) {
            int j = i+l;
            d[i][j] = inf;
            for (int k=p[i][j-1]; k<=p[i+1][j]; k++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    p[i][j] = k;
                }
            }
            d[i][j] += a[j]-a[i];
        }
    }
    cout << d[0][n-1];
}