[백준/BOJ] 9251번 LCS (C/C++)

백준 온라인 저지(BOJ) 9251번 LCS
https://www.acmicpc.net/problem/9251

* 사용언어 : C언어, C++
 

1. 문제

주어지는 두 문자열에 대해서 LCS(Longest Common Subsequence)의 길이를 출력

 

2. 풀이

혼자 고민하다가 구글링을 해봤는데 놀라운 퀄리티의 자료를 발견해서 한 방에 이해했습니다.
해당 게시글을 통해 내용을 이해한 덕분에 구현도 쉽게 할 수 있었습니다.
https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 
 
풀이 방법을 간단히 요약하여 설명해보겠습니다.
우선 LCS라는 2차원 int 배열을 만들고
i는 1부터 n1까지, j도 1부터 n2까지 순회하면서 모든 문자들을 순서대로 비교합니다.

 

비교하면서 LCS[i][j]에 값을 넣어주는데, 
문자가 같을 때는 LCS[i - 1][j - 1]에 1을 더한 값을 저장하고
다를 때는 LCS[i - 1][j], LCS[i][j - 1] 중 큰 값을 저장합니다.
 
위 논리로 구현하게 된 구체적인 설명은 위 링크에서 읽어보시는 것을 추천드립니다.
그 외 코드 구현 자체는 단순하니 풀이는 생략하겠습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9251_LCS
*/
#include <cstdio>

const int LM = 1001;
char s1[LM], s2[LM];
int LCS[LM][LM], l1, l2, ret;

int strlen(char *s) {
	int len = 0;
	while (*s++) len++;
	return len;
}

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

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%s", s1);
	scanf("%s", s2);

	l1 = strlen(s1);
	l2 = strlen(s2);

	for (int i = 1; i <= l1; ++i) {
		for (int j = 1; j <= l2; ++j) {
			if (s1[i - 1] == s2[j - 1]) LCS[i][j] = LCS[i - 1][j - 1] + 1;
			else LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j]);

			if (LCS[i][j] > ret) ret = LCS[i][j];
		}
	}

	printf("%d\n", ret);
	return 0;
}