[백준][C++] 9251 LCS

 

 

 

알고리즘 종류

    - 문자열

    - DP

 

 

 

사고 과정

    - LCS 알고리즘이다.

    - 문자열 A와 문자열 B의 문자를 하나씩 비교하면서 같은 문자이면 숫자를 센다.

    - 시각화된 자료는 이 블로그를 참고했다.

 

 

 

구현(C++)

#include <iostream>
#include <stdio.h>
#include <string>
 
using namespace std;
 
// 같은 문자 개수 세기
int dp[1001][1001];
 
int main(void){
    
    string str1;
    string str2;
    
    cin >> str1 >> str2;
    
    // 각각의 문자를 비교하기
    for(int i=1; i<=str1.length(); i++){
        for(int j=1; j<=str2.length(); j++){
            // 문자가 같으면, dp에 저장된 이전 개수를 가져와서 +1 해주기
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            // 다르면, 이전 것들 중에 가장 큰 것 가져오기
            else {
                dp[i][j] = max(max(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
            }
        }
    }
    
    // dp 마지막에 기록된 개수 가져오기
    cout << dp[str1.length()][str2.length()] << endl;
 
}
 
 
 

 

 

 

시행착오

    - 이전에 LCS를 풀었지만, 알고리즘이 생각나지 않아서 다시 풀어보았다.