[ BOJ 백준 9251번 - LCS ] 해설 및 코드

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

 

목적

최장 공통 부분 수열(LCS)를 구하자.  ACAYKP와 CAPCAK의 LCS는 ACAK이다.

 

접근법

1. 문자열 a와 b가 입력으로 주어질 때, s[i][j]는 a문자열의 i번째, b문자열의 j번째까지의 LCS라고 가정한다.

2. 그러면 s[i][j]는 다음 세 가지 결과 값의 최대값이다. s[i][j-1], s[i-1][j], s[i-1][j-1]+(a[i]==b[j])

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int s[1001][1001];
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string a, b; cin >> a >> b;
    s[0][0] = (a[0] == b[0]);
    f(j, 1, b.length())s[0][j] = (a[0] == b[j]) ? 1 : s[0][j - 1];
    f(i, 1, a.length())s[i][0] = (a[i] == b[0]) ? 1 : s[i - 1][0];
    f(i, 1, a.length())f(j, 1, b.length())
        s[i][j] = max((a[i] == b[j]) + s[i - 1][j - 1], max(s[i][j - 1], s[i - 1][j]));
    cout << s[a.length() - 1][b.length() - 1];
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.