11056번: 두 부분 문자열

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

$O(l_al_b)$

답은 (a 길이) + (b 길이) - (LCA(a,b) 길이)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[1002], b[1002];
int dp[1001][1001], n, m;
int main() {
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for (int i = 1; a[i]; i++)
        for (int j = 1; b[j]; j++)
            dp[i][j] = max({ dp[i - 1][j - 1] + (a[i] == b[j]),dp[i - 1][j],dp[i][j - 1] });
    printf("%d", n + m - dp[n][m]);
    return 0;
}

7977번: 크리스 마틴

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


$O(n)$

제일 빈도가 작은 문자를 n번 출력하면 된다.
그러한 문자가 문자열 안에 c개 존재한다 해보자.
마틴의 문자열 안의 각 문자는 c개 보다 작아야 한다.
그럼, (마틴의 문자열 길이)<4*c<=n 모순.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s[4], idx;
char c;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %c", &c);
        if (c == 'A') s[0]++;
        if (c == 'C') s[1]++;
        if (c == 'G') s[2]++;
        if (c == 'T') s[3]++;
    }
    idx = min_element(s, s + 4) - s;
    printf("%d\n", s[idx]);
    for (int i = 0; i < n; i++) putchar("ACGT"[idx]);
    return 0;
}

13711번: LCS 4

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


$O(N\lg N)$

Ai를 i로 바꿔 생각하면 LIS를 구하는 문제와 동치이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int idx[MXN + 1], dp[MXN], n, x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        dp[i] = n;
        *lower_bound(dp, dp + i, idx[x]) = idx[x];
    }
    printf("%d", lower_bound(dp, dp + n, n) - dp);
    return 0;
}

9251번: LCS

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


$O(nm)$

최장 공통 부분 수열의 길이를 구하는 문제이다.
dp[i][j]: 문자열 s1[1...i] 과 s2[1...j]의 최장 공통 부분 수열 길이
dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(s1[i]==s2[j]))

#include<cstdio>
#include<algorithm>
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = std::max({ dp[i][j - 1],dp[i - 1][j],dp[i - 1][j - 1] + (s1[i] == s2[j]) });
    printf("%d", dp[i - 1][j - 1]);
    return 0;
}

9252번: LCS 2

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

$O(nm)$

LCS 구현

#include<cstdio>
#include<algorithm>
using namespace std;
char s1[1002], s2[1002];
int dp[1001][1001];
void f(int x, int y) {
    if (!dp[x][y]) return;
    if (s1[x] == s2[y]) {
        f(x - 1, y - 1);
        putchar(s1[x]);
    }
    else dp[x - 1][y] > dp[x][y - 1] ? f(x - 1, y) : f(x, y - 1);
}
int main() {
    scanf("%s%s", s1 + 1, s2 + 1);
    int i, j;
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = max({ dp[i - 1][j - 1] + (s1[i] == s2[j]),dp[i - 1][j],dp[i][j - 1] });
    printf("%d\n", dp[--i][--j]);
    f(i, j);
    return 0;
}

2612번: DNA 유사도

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


$O(nm)$

lcs 비슷하게 풀면 된다.
문자열 s1[1...n], s2[1...m]이 주어졌을 때
dp[i][j]=부분 서열 s1[...i]과 s2[...j] 사이 최대 유사도
이 값은 다음 중 최댓값

1. s1[...i-1] + s1[i] / s2[...j-1] + s2[j]
-> dp[i-1][j-1] + (s1[i]==s2[j]이면 3 아니면 -2)
2. s1[...i] + ' ' / s2[...j-1] + s2[j]
-> dp[i][j-1]-2
3. s1[...i-1] + s1[i] / s2[...j] + ' '
-> dp[i-1][j]-2
4. s1[i] / s2[j] 즉, 시작지점
-> s1[i]==s2[j]이면 3 아니면 -2

dp 테이블 중 최댓값을 출력하고 시작지점을 찾아 부분서열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int l1, l2, dp[1001][1001], maxi, px, py;
pair<int, int> fr[1001][1001];
char s1[1002], s2[1002];
int main() {
    scanf("%d%s%d%s", &l1, s1 + 1, &l2, s2 + 1);
    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (s1[i] == s2[j]) dp[i][j] = 3, fr[i][j] = { i,j };
            int t = dp[i - 1][j - 1] + (s1[i] ^ s2[j] ? -2 : 3);
            if (dp[i][j] < t) {
                dp[i][j] = t;
                fr[i][j] = fr[i - 1][j - 1];
            }
            if (dp[i][j] < dp[i - 1][j] - 2) {
                dp[i][j] = dp[i - 1][j] - 2;
                fr[i][j] = fr[i - 1][j];
            }
            if (dp[i][j] < dp[i][j - 1] - 2) {
                dp[i][j] = dp[i][j - 1] - 2;
                fr[i][j] = fr[i][j - 1];
            }
            if (maxi < dp[i][j]) {
                maxi = dp[i][j];
                px = i; py = j;
            }
        }
    }
    s1[px + 1] = s2[py + 1] = 0;
    printf("%d\n%s\n%s", maxi, s1 + fr[px][py].first, s2 + fr[px][py].second);
    return 0;
}

1958번: LCS 3

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


$O(lmn)$

2차원 lcs dp를 응용한다.

#include<cstdio>
#include<algorithm>
char s1[102], s2[102], s3[102];
int dp[101][101][101], i, j, k;
int main() {
    scanf("%s %s %s", s1 + 1, s2 + 1, s3 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            for (k = 1; s3[k]; k++)
                dp[i][j][k] = std::max({ dp[i - 1][j - 1][k - 1] + (s1[i] == s2[j] && s1[i] == s3[k]),dp[i - 1][j][k],dp[i][j - 1][k],dp[i][j][k - 1] });
    printf("%d", dp[i - 1][j - 1][k - 1]);
    return 0;
}