본문 바로가기

코딩/백준 BOJ

[백준/C언어] 9251번 - LCS

백준 웹사이트 "9251번 - LCS" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 


문제

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net


소스 코드

#include <stdio.h>
#include <string.h>
int max(int a, int b);
int main(void){
char string1 [1001];
char string2 [1001];
scanf("%s", &string1);
scanf("%s", &string2);
int string1_len = strlen(string1);
int string2_len = strlen(string2);
//LCS 배열: LCS[i][j]는 string1의 i번째 문자, string2의 j번째 문자에서의 LCS
int LCS[string1_len+1][string2_len+1];
for(int i=0; i<string1_len+1; i++){
LCS[i][0] = 0;
}
for(int j=0; j<string2_len+1; j++){
LCS[0][j] = 0;
}
for(int i=1; i<string1_len+1; i++){
for(int j=1; j<string2_len+1; j++){
if(string1[i-1] == string2[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(" ");
for(int j=0; j<string2_len+1; j++){
printf("%c ", string2[j]);
}
printf("\n");
for(int i=0; i<string1_len+1; i++){
if(i==0)
printf(" ");
else
printf("%c ", string1[i-1]);
for(int j=0; j<string2_len+1; j++){
printf("%d ", LCS[i][j]);
}
printf("\n");
}
*/
printf("%d\n", LCS[string1_len][string2_len]);
}
int max(int a, int b){
if(a>b)
return a;
else
return b;
}

문제 풀이

  

반응형