티스토리 뷰

알고리즘 관련/BOJ

BOJ)9252 LCS 2

JASON 자손9319 2017. 2. 2. 20:30

문제: icpc.me/9252


LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다.


dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다.


점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 


소스코드에서는 테이블의 정의를 반대로 사용하였다.


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
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
string a, b;
int dp[1001][1001];
pair<intint> back[1001][1001];
int alen, blen;
int func(int i, int j){
    if (alen == i || blen == j)return 0;
    int& ret = dp[i][j];
    if (ret != -1)return ret;
    if (a[i] == b[j]) {
        back[i][j] = { i + 1,j + };
        return ret = + func(i + 1, j + 1);
    }
    int x = func(i + 1, j);
    int y = func(i, j + 1);
    if (x > y) {
        back[i][j] = { i + 1,j };
        return ret = x;
    }
    else {
        back[i][j] = { i,j + };
        return ret = y;
    }
}
int main(){
    cin >> a >> b;
    alen = a.size();
    blen = b.size();
    memset(dp, -1sizeof(dp));
    printf("%d\n", func(00));
    int x, y;
    x = y = 0;
    while (x != alen&&!= blen) {
        if (a[x] == b[y])
            printf("%c", a[x]);
        int tx = x;
        x = back[x][y].first;
        y = back[tx][y].second;
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5052 전화번호 목록  (0) 2017.02.03
BOJ)2662 기업투자  (0) 2017.02.03
BOJ)9252 LCS 2  (0) 2017.02.02
BOJ)1701 Cubeditor  (0) 2017.02.01
BOJ)11585 속타는 저녁 메뉴  (0) 2017.02.01
BOJ)4354 문자열 제곱  (0) 2017.02.01
댓글
댓글쓰기 폼