[백준/9251] LCS (Longest Common Subsequence) 문제풀이

1. 문제

 

 

 

2. 접근 방법

 

다이나믹 프로그래밍 문제이다.

이틀에 걸쳐 다양한 접근 방법을 생각해보았으나, 결국 내 능력의 한계로 풀지 못해서 답을 봐야만 했다.

나에게 좌절감을 안겨준 문제이자, 동시에 자극을 준 문제이기도 하다. (더 열심히 해야겠다!)

 

어쨌든... 접근 방법은 다음과 같다.

 

위와 같이, 비교 대상인 두 문자를 각각 행과 열로 가지는 배열을 생성한다.

여기에서는 각 시작 문자 앞에 '0' 을 추가하여 0번 행과 열은 모두 0의 값을 가지게 한다. (계산을 위함)

그 후, Z의 순서로 계산을 해나가면 되는데, i행 j열의 계산 방법은 다음과 같다.

 

(1) 행과 열의 문자가 일치할 경우

= 좌 대각선 위의 값 + 1

→ 문자가 일치하므로, 이전까지의 LCS에 1을 더하기 위함이다. 즉, 이전까지의 LCS가 좌 대각선의 값임

 

(2) 행과 열의 문자가 일치하지 않을 경우

= 왼쪽 값, 위의 값 중 더 큰 값을 그대로 갖는다.

→ 문자가 불일치하므로, 비교한 문자가 포함되어 있는 직전 LCS의 값을 그대로 가져온다.

 

이런 식으로 계산을 진행하다보면 다음과 같이 배열이 만들어진다.

 

 

여기에서 최종으로 만들어지는 숫자가 두 문자의 LCS가 된다. 여기에서는 4의 값을 가진다.

각 중에서 최초로 숫자의 변화가 이루어지는 열 중, 가장 열의 번호가 빠른 것들을

체크해나가다보면 LCS의 문자를 확인할 수 있다.

여기에서는 'ACAK' 임을 알 수 있다.

 

 

3. 코드

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

char s1[1001], s2[1001];
int dp[1001][1001];

int main(void)
{
	scanf("%s %s", s1 + 1, s2 + 1);

	int i, j;
	for (i = 1; s1[i]; i++)
		for (j = 1; s2[j]; j++)
			if (s1[i] == s2[j])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}

	printf("%d\n", dp[i - 1][j - 1]);

	return 0;
}