[백준 9251번] LCS

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

9251번: LCS

풀이) 

(여담으로 학교 알고리즘수업때 시험문제로도 나왔었던 문제이다.)

 

앞선 문자열들의 결과가 존재해야 해당 순간에 맞는 가장 긴 값을 dp배열에 저장할 수 있기 때문에 dp는 (1, 1)배열부터 시작한다. 

부분 문자열A와 부분 문자열B를 비교한다고 했을 때, 2가지 경우를 기준으로 dp에 값을 채울 수 있다.

 

1) 부분 A문자열의 마지막 인덱스값과 부분 문자열B의 마지막 인덱스값이 같은 경우

예를 들면 "ACA", "CA" 가 있다. 이 경우 마지막 A가 같기 때문에 두 부분 문자열에서 맨 마지막 문자열("A")가 빠졌던 ("AC", "C") 경우에서 길이가 1이 증가된 경우라고 볼 수 있다. 또 "AC", "C"의 경우 또한 "C"가 같기때문에 "A", ""의 경우에서 1이 증가된 경우라고 볼 수 있다. 위의 규칙에서 볼 수 있듯 마지막 인덱스값이 같은 경우 직전 경우에서 1이 증가된 값이 해당 dp의 값이 된다.

 

2) 부분 A문자열의 마지막 인덱스값과 부분 문자열B의 마지막 인덱스값이 다른 경우

예를 들면 "ACA", "CAP"가 있다. 이 경우 마지막 값이 다르다. 그렇기 때문에 이 문자열들로 만들 수 있었던 가장 큰 값을 해당 값으로 넣어주어야 한다. 그렇기 때문에 "ACA", "CA"의 경우와 "AC", "CAP"의 경우 중 더 긴 경우를 해당 dp의 값으로 넣어주면 된다.  

 

(위의 설명을 토대로 직접 종이와 펜을 가지고 dp의 값들을 비교해보며 채워가면 쉽게 이해가 될 수 있다.)

#include <iostream>
using namespace std;

string a, b;
int LCS[1001][1001];

void solve()
{
    for (int i = 1; i <= a.size(); i++)
    {
        for (int j = 1; j <= b.size(); j++)
        {
            if (a[i - 1] == b[j - 1])
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            else
                LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j]);
        }
    }
    cout << LCS[a.size()][b.size()];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> a >> b;
    solve();
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!