[C++] 9251번 LCS

문제

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

 

 

 

 

코드

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

int main() {
    // 1. 입력 처리: 두 문자열을 공백 기준으로 입력받아 s1, s2에 저장
    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.size(), m = s2.size();
    // 2. DP 배열 선언: 이전 행을 저장할 temp와 현재 행을 저장할 next
    vector<int> temp(m + 1);
    vector<int> next(m + 1);

    // 3. LCS 길이 계산 반복문
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 3-1. 문자가 같으면 대각선 값 + 1
            if (s1[i - 1] == s2[j - 1])
                next[j] = temp[j - 1] + 1;
            // 3-2. 다르면 왼쪽 혹은 위쪽 값 중 최대값 선택
            else
                next[j] = max(temp[j], next[j - 1]);
        }
        // 3-3. 현재 행을 이전 행으로 교체
        swap(temp, next);
    }

    // 4. 결과 출력: 최종 LCS 길이를 출력
    cout << temp[m] << endl;

    return 0;
}

 

 

 

풀이

 

1. 입력 처리:
   • cin >> s1 >> s2를 통해 두 문자열을 입력받아 각각 s1, s2에 저장
2. DP 배열 초기화:
   • temp와 next 벡터를 길이 m+1로 선언하여, 이전 행과 현재 행의 LCS 값을 저장할 공간 확보
3. LCS 계산:
   1. 외부 반복문(i = 1 … n): s1의 각 문자에 대해
   2. 내부 반복문(j = 1 … m): s2의 각 문자에 대해
      • s1[i-1] == s2[j-1]인 경우, 대각선(temp[j-1]) 값에 1을 더해 next[j]에 저장
      • 그렇지 않은 경우, 위(temp[j])와 왼쪽(next[j-1]) 중 큰 값을 next[j]에 저장
   3. 한 행 계산이 끝나면 swap(temp, next)로 next를 temp로 옮겨 다음 반복에서 사용
4. 출력:
   • 최종적으로 temp[m]에 저장된 값이 두 문자열의 최장 공통 부분 수열 길이이므로 이를 출력