[백준 / BAEKJOON] 9251번 LCS - C++

문제 원문

조건

시간 제한 : 1초
메모리 제한 : 256 MB

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제

풀이

동적계획법을 활용하여 푸는 문제입니다.

가장 공통인 문자열의 길이를 구하는 문제이므로

처음엔 DP 배열을 1차원 배열로 사용하여

문자가 일치할때     : DP[i] = DP[i] + 1
문자가 불일치 할때 : DP[i] = max( DP[i], DP[i -1])

위와 같은 점화식으로 풀어봤지만 예시는 답이 나와도 틀렸다고 나오더군요

알아보니 2차원 배열을 사용하여 이전 문자를 탐색한 결과를 바탕으로 점화식을 진행해야 됐습니다.

탐색은 문자열A, 문자열B를 각각 i, j 변수로 탐색하고 문자열A의 문자를 하나씩 문자열B의 문자 모두와 비교하여 진행합니다.

결과적으로 최종 점화식은 다음과 같습니다.

문자가 일치할때     : DP[i][j] = DP[i - 1][j - 1] + 1
문자가 불일치 할때 : DP[i][j] = max( DP[i - 1][j], DP[i][j -1])

성공 코드

#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	string strA, strB;
	cin >> strA >> strB;

	vector<vector<int>> vDp(strA.size() + 1, vector<int>(strB.size() + 1, 0));
	int nMax = 0;
	for (int i = 1; i <= strA.size(); i++)
	{
		for (int j = 1; j <= strB.size(); j++)
		{
			if (strA[i - 1] == strB[j - 1])
				vDp[i][j] = vDp[i - 1][j - 1] + 1;
			else
				vDp[i][j] = max(vDp[i - 1][j], vDp[i][j - 1]);
		}
	}

	cout << vDp[strA.size()][strB.size()] << '\n';

	return 0;
}

결과

Github - github.com/ledpear