[백준] 9251 C++ LCS (DP, 문자열)

- 문제 설명

 

 

- 문제 풀이

문제가 간단해 보이는듯 하면서도 배열을 적어보지 않으면 규칙을 찾기가 꽤 까다로웠다.

 

이 문제는 2차원 배열을 이용하여 풀어낼 수 있다.

이를 DP로 한다 하고 크기를 첫째 줄의 문자열의 길이 x 둘째 줄의 문자열의 길이로 해 선언해 준다.

이를 DP[i][j]라 했을때 0부터 i번째 문자열과 0부터 j번째 문자열 까지의 공통 부분 수열의 갯수를 넣어준다.

 

예제와 같이 ACAYKP, CAPCAK를 예로 든다면 아래 표와 같다.

DP

 

행열의 첫째 줄은 0으로 한다고 가정하자. 형광칠 된 곳은 i번째 문자와 j번째 문자가 같은 지점이다.

표를 보면 규칙을 찾을 수 있는데

 

1. i번째 문자와 j번째 문자가 같다면 DP[i-1][j-1] + 1 을 한 것과 같다는 규칙 (대각선 위의 DP값 + 1)

2. i번째 문자와 j번째 문자가 다르다면 DP[i-1][j], DP[i][j-1] 중 큰 값과 같다는 규칙(왼쪽 혹은 윗 값중 큰 것)

 

이 규칙을 깨닫는다면 코드로 구현하는 것은 간단하다.

 

 

 

- 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string A, B;
int DP[1001][1001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> A >> B;

	for (int i = 0; i < A.length(); i++)
	{
		for (int j = 0; j < B.length(); j++)
		{
			if (A[i] == B[j]) // 문자가 같다면
			{
				DP[i + 1][j + 1] = DP[i][j] + 1; // 왼쪽위 대각선 값 + 1
			}
			else
			{
				DP[i + 1][j + 1] = max(DP[i][j + 1], DP[i + 1][j]); // 왼쪽 혹은 윗 값중 큰 값
			}
		}
	}

	cout << DP[A.length()][B.length()];

	return 0;
}