[C++] 백준 9251 - LCS

• 문제

• 풀이 과정

• 최종 코드

• 잡담

백준 9251 : LCS
난이도 : 골드 5

시간 : 해결 x

 

 

 

문제

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

9251번: LCS

풀이 과정

문제 특성상 이전값에서 +1를 하면 되겠다라는 생각을 했지만 정확한 기준을 파악하지 못했다.

if문 범벅이 되는 걸 보고 이건 도저히 아니겠다 싶어 정답을 참고했다.

 

 

풀이 과정은 생각보다 간단했다.

2차원 배열을 만들어 각각의 문자열 속의 문자를 원소로 하여 검사를 하면 됐다.

 

만약 n번째 문자열을 비교했을 때 서로 같으면 +1를 한다.

서로 다르면 왼쪽이나, 위쪽 값 중에 큰 값을 저장한다.

 

 

최종 코드

#include <iostream>
#include <cstring>
using namespace::std;

#define MAX 1001

int lcs[MAX][MAX];

string s1;
string s2;

int Max(int a, int b){
    return a>b ? a : b;
}

int main(){
    cin >> s1 >> s2;
    lcs[0][0] = 0;
    for (int i = 0; i <= s1.length(); i++){
        lcs[i][0] = 0;
    }
    for (int i = 0; i <= s2.length(); i++){
        lcs[0][i] = 0;
    }
    
    for(int i=1; i<=s1.length(); i++){
        for(int j=1; j<=s2.length(); j++){
            if(s1[i-1] == s2[j-1]){
                lcs[i][j] = lcs[i-1][j-1] + 1;
            }else{
                lcs[i][j] = Max(lcs[i-1][j], lcs[i][j-1]);
            }
        }
    }
    printf("%d\n", lcs[s1.length()][s2.length()]);
    
}

 

 

 

잡담

dp는 같은 난이도 중에서 제일 어려운 카테고리 같다..