백준, BOJ, 9251번, LCS : C++ [CPP]

어려웠다.

부분으로 쪼갤 수 있었지만 생각이 잘 안났다.

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

 

---

 

모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다.

DP문제라는 것을 한 번에 파악할 수 있었다.

 

어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다.

 

처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다.

마지막부터 조사했어야 했다.

 

길이가 L1, L2의 문자열이 있다.

만약 마지막 부분이 같다면

해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다.

 

마지막 부분이 다르다면

둘 다 제외하는 것이 아닌

L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다.

 

그리고 문자열이 비어있는 것과의 LCS값은 항상 0이 나와야만 했다.

 

이렇게 나눈 것을 코딩하기가 조금 힘들었다.

 

한 번 보자

#include <iostream>
#include <string>

using namespace std;

//문자열
string s1,s2;
int l1,l2;

//LCS(a,b) 의 값을 저장하기 위한 dp table
//LCS (x,y) = LCS(x',y') ... 으로 쪼개서 풀기 위함
int dp[1002][1002];

void init(){
    cin.tie(0);
    ios::sync_with_stdio(0);
}

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

int main(){
    init();
    getline(cin,s1);
    getline(cin,s2);
    l1 = s1.length();
    l2 = s2.length();
    
    //등호가 붙은 것은 부분집합 중 공집합도 포함시키기 위함이다.
    for(int i = 0; i<=l1; i++){
        for(int j = 0; j<=l2; j++){
            
            //공집합과의 부분비교는 항상 0의 길이가 나온다.
            if(i == 0 || j == 0){
               dp[i][j] = 0;
               continue; 
            }
            //다르다면 둘 중 어느 한쪽의 문자열을 제외하고 비교한다.
            if(s1[i-1] != s2[j-1]){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }else{
                //같다면 둘다 제외하고 나머지 문자열의 LCS를 구한다.
                dp[i][j] = dp[i-1][j-1]+1;
            }
        }
    }
    
    
    cout << dp[l1][l2];
    

    
}

 

항상 여기서의 핵심은

문제를 쪼갤 수 있느냐이다.

그리고 어떻게 쪼개느냐이다.

문자열의 끝만 비교해서 점차 작은 문제로 나눈다는 생각을 하기가 제일 어려웠다.

이 문제에서 가장 시간이 오래걸리는 부분이었다.

시간의 90%정도를 문자열 끝을 비교하는 것을 생각하는 데에 썼다.