백준 웹사이트 "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; }
문제 풀이
반응형
'코딩 > 백준 BOJ' 카테고리의 다른 글
[백준/C언어] 12865번 - 평범한 배낭 (4) | 2022.03.17 |
---|---|
[백준/C언어] 1912번 - 연속합 (0) | 2022.03.16 |
[백준/C언어] 2565번 - 전깃줄 (0) | 2022.03.14 |
[백준/C언어] 11054번 - 가장 긴 바이토닉 부분 수열 (0) | 2022.03.13 |
[백준/C언어] 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2022.03.12 |