7. dp - LCS

7.md

0.01MB

0. 복습

boj.kr/13301, boj.kr/17391

1. LCS(Longest Common Subsequence)

ACAYKP, CAPCAK이 있을 때 최장 공통 부분 문자열을 구해보자.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

dp[i][j] = 첫번째 문자열의 i번째, 두번째 문자열의 j번째까지 봤을 때 가장 긴 공통 부분 문자열

arr[i] == arr[j] 일 때 dp[i][j] = dp[i-1][j-1] + 1;

arr[i] != arr[j] 일 때 dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

참고 문제 : boj.kr/9251, boj.kr/3793, boj.kr/5582, boj.kr/5502, boj.kr/1695, boj.kr/1958, boj.kr/9252, boj.kr/14002/, boj.kr/12852

99. 부록 : 참고 문제 풀이

• boj.kr/13301

#include <iostream>
using namespace std;
typedef long long int ll;
ll arr[100];
ll dp[100];

int main(){
    ll N; cin >> N;
    arr[1]=1;
    arr[2]=1;
    dp[1]=4;
    dp[2]=6;

    for(int i=3; i<=N; ++i){
        arr[i]=arr[i-1]+arr[i-2];
        dp[i]=dp[i-1]+arr[i]*2;
    }
    cout << dp[N] << '\n';

}

• boj.kr/17391

#include <iostream>
using namespace std;
int arr[301][301];
int dp[301][301];
int main(){
    int N, M; cin >> N >> M;
    dp[1][1] = 0;
    for(int i=1; i<=N; ++i){
        for(int j=1; j<=M; ++j){
            cin >> arr[i][j];
            int res=987654321;

            for(int k=1; k<=i-1; ++k){
                if(k+arr[k][j]>=i) res=min(res, dp[k][j]+1);
            }
            for(int k=1; k<=j-1; ++k){
                if(k+arr[i][k]>=j) res=min(res, dp[i][k]+1);
            }
            if(!(i==1 && j==1)) dp[i][j]=res;
        }
    }
    cout << dp[N][M] << '\n';
}

//dp[i][j] = i, j가 도착 지점일 때 부스터의 최소 개수
//dp[i][j] = min(dp[1~i-1][j]+1, dp[i][1~j-1]+1), 단, 이동 가능해야 함.

• boj.kr/9251

#include <iostream>
#include <string>
using namespace std;

int dp[4001][4001];

int main(){
    string a, b; cin >> a >> b;
    for(int i=0; i<a.size(); ++i){
        for(int j=0; j<b.size(); ++j){
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }
    cout << dp[a.size()][b.size()] << '\n';
}

• boj.kr/3793

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int dp[4001][4001];

int main(){

    char a[1000], b[1000];
    while(scanf("%s %s", a, b) != EOF){
        for(int i=0; i<=4000; ++i){
            for(int j=0; j<=4000; ++j){
                dp[i][j] = 0;
            }
        }
        for(int i=0; a[i]!=0; ++i){
            for(int j=0; b[j]!=0; ++j){
                if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
                else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }

        cout << dp[strlen(a)][strlen(b)] << '\n';
    }
}

• boj.kr/5582

#include <iostream>
#include <string>
using namespace std;

int dp[4001][4001];
int res=-1;

int main(){
    string a, b; cin >> a >> b;
    for(int i=0; i<a.size(); ++i){
        for(int j=0; j<b.size(); ++j){
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1] = 0;
            res=max(res, dp[i+1][j+1]);
        }
    }
    cout << res << '\n';
}

• boj.kr/5502

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[5001][5001];

int main(){
    int N; cin >> N;
    string a; cin >> a;
    string b=a;
    reverse(b.begin(), b.end());
    for(int i=0; i<a.size(); ++i){
        for(int j=0; j<b.size(); ++j){
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }
    cout << a.size()-dp[a.size()][b.size()] << '\n';

}

• boj.kr/1695

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[5001][5001];
int a[5001];
int b[5001];

int main(){
    int N; cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> a[i];
        b[N-i+1] = a[i];
    }
    for(int i=1; i<=N; ++i){
        for(int j=1; j<=N; ++j){
            if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << N-dp[N][N] << '\n';
}

• boj.kr/1958

#include <iostream>
#include <string>
#define max6(a, b, c, d, e, f) max((a), max((b), max((c), max((d), max((e), (f))))))
using namespace std;
int dp[101][101][101];
int main(){
    string a, b, c; cin >> a >> b >> c;
    for(int i=1; i<=a.size(); ++i){
        for(int j=1; j<=b.size(); ++j){
            for(int k=1; k<=c.size(); ++k){
                if(a[i-1] == b[j-1] && b[j-1] == c[k-1]) dp[i][j][k] = dp[i-1][j-1][k-1]+1;
                else dp[i][j][k] = max6(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1], dp[i-1][j-1][k], dp[i][j-1][k-1], dp[i-1][j][k-1]);
            }
        }
    }
    cout << dp[a.size()][b.size()][c.size()] << '\n';
}

• boj.kr/9252

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[4001][4001];
string res = "";

int main(){
    string a, b; cin >> a >> b;
    for(int i=0; i<a.size(); ++i){
        for(int j=0; j<b.size(); ++j){
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
            else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }
    cout << dp[a.size()][b.size()] << '\n';
    int i=a.size(), j=b.size();
    while(1) {
        if(dp[i][j] == 0) break;
        if(dp[i-1][j] == dp[i][j]){
            i-=1;
            continue;
        }
        if(dp[i][j-1] == dp[i][j]) {
            j-=1;
            continue;
        }
        res+=a[i-1];
        i-=1; j-=1;
    }
    reverse(res.begin(), res.end());
    cout << res << '\n';
}

• boj.kr/14002

#include <iostream>
#include <vector>
using namespace std;
int arr[1001];
int dp[1001];
int maxcnt=-1;
vector<int> v;
int main(){
    int N; cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> arr[i];
        if(i==1) dp[i]=1;
        int res=1;
        for(int j=1; j<i; ++j){
            if(arr[i]>arr[j]) res=max(res, dp[j]+1);
        }
        dp[i]=res;
        maxcnt=max(dp[i], maxcnt);
    }
    cout << maxcnt << '\n';
    int key=maxcnt;
    for(int i=N; i>=1; --i){
        if(key==0) break;
        if(dp[i] == key) {
            v.push_back(arr[i]);
            key--;
        }
    }
    for(int i=v.size()-1; i>=0; --i){
        cout << v[i] << " ";
    }
    cout << '\n';
}

• boj.kr/12852

#include <iostream>
#include <string>
using namespace std;
int dp[1000001];
int solve(int n){
    if(dp[n]) {
        return dp[n];
    }
    if(n==1) {
        return 0;
    }
    if(n%3==0){
        if(n%2==0){
            return dp[n]=min(solve(n/3), min(solve(n/2), solve(n-1)))+1;
        }
        else {
            return dp[n] = min(solve(n/3), solve(n-1))+1;
        }
    }
    else if(n%2==0) {
        return dp[n] = min(solve(n/2), solve(n-1))+1;
    }
    else return dp[n] = solve(n-1)+1;
}
int main(){
    int N; cin >> N;
    cout << solve(N) << '\n';
    while(N!=1) {
        if(N%3==0 && dp[N]==dp[N/3]+1){
            cout << N << ' ';
            N/=3;
        }
        else if(N%2==0 && dp[N] == dp[N/2]+1) {
            cout << N << ' ';
            N/=2;
        }
        else{
            cout << N << ' ';
            N-=1;
        }
    }
    cout << "1" << '\n';
}