[백준] LCS 9251번 (c++)

출처 : 9251번: LCS (acmicpc.net)

9251번: LCS

풀이 방법

비슷한 문제를 풀어봐서 쉽게 접근 할 수 있었다.

2차원 배열을 만든 뒤 i인덱스는 문자열 0부터 i까지의 문자열1과  0부터 j까지 문자열2 까지의 LCS를 

구한 것이다.

배열에서 만약 i인덱스 문자와 j문자의 인덱스가 같으면 i-1, j-1인덱스 의 값에 +1 한 것이고.

만약 다르다면 i-1, j or i, j-1 의 값중 큰 값을 넣으면 된다.

#include<bits/stdc++.h>

// 백준 9251번

using namespace std;

int cnt[1001][1001];
string str1, str2;
int ans = 0;

int match(char c1, char c2) {
    if (c1 == c2) return 1;
    else return 0;
}
void dp(int i, int j) {
    if (str1[i] == str2[j]) {
        cnt[i+1][j+1] = cnt[i][j] + 1;
    }
    else {
        cnt[i+1][j+1] = max(cnt[i][j+1], cnt[i+1][j]);
    }
    if (cnt[i+1][j+1] > ans) ans = cnt[i+1][j+1];


}

int main(){
    cin >> str1 >> str2;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < str1.size();i++) {
        for (int k = 0; k < str2.size();k++) {
                dp(i, k);
        }
    }
    cout << ans;

    return 0;
}