[문제 링크]



LCS는 다음 포스트에 있는 내용과 같다.


http://hsp1116.tistory.com/37




#include <cstdio>
#include <algorithm>
#include <cstring>
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(){
    int n = strlen(compare), m = strlen(input);
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=n;i++){
        for(int j=1; j<=m;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[n][m];
}
int main(){
    scanf("%s %s",input,compare);
    printf("%d\n",LCS());
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1753 최단경로  (1) 2016.04.22
백준 - 9252 LCS 2  (0) 2016.04.17
백준 - 9251 LCS  (0) 2016.04.17
알고스팟 - KOOGLE  (0) 2016.04.14
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28

+ Recent posts