[C언어] 백준 9251 : LCS

흐름

LCS가 무엇인지부터 알아보았다.
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
진짜 미친 설명이다.
최장 공통 부분 수열의 최대값, 수열, 공통 문자열까지 하나부터 설명을 해주신다.

위 벨로그의 일부분인데, 이 아이디어로 최댓값을 출력할 것이다.
간단히 설명해서, 공통된 게 있다면 왼쪽 대각선을 기준으로 +1을 해주고,
공통된게 없다면 자신의 왼쪽과 위 중 최댓값을 가지고 간다.
결국에 마지막 칸에는 최대숫자가 나오게 될테니, 그거를 출력해버린다.

내가 푼 코드

#include <stdio.h>
#include <string.h>
#define max(a, b) (a > b ? a : b)

int LCS[1002][1002];
char str[1002];
char str2[1002];

int main()
{
	scanf("%s %s", str, str2);
	int i, j;
	i = 1;
	while (i <= strlen(str))
	{
		j = 1;
		while (j <= strlen(str2))
		{
			if (str2[j - 1] == str[i - 1])
			{
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			}
			else
			{
				LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
			}
			j++;
		}
		i++;
	}
	printf("%d", LCS[i - 1][j - 1]);
}