백준 9251번 LCS C/C++ 풀이

https://www.acmicpc.net/problem/9251

9251번: LCS

DP 문제, 그 중에서도 2차 배열을 이용하면 쉽게 풀 수 있다.

 

각각의 string 글자 수를 가진 2차 배열을 만들어서 각각의 cell을 채워나간다.

 

각각의 글자가 같지 않을 때는 왼쪽이나 위(i나 j가 같은) 중에서 크기가 큰 열을 선택하고, 같은 상황이 온다면 왼쪽 위에서 1을 더한 뒤 왼쪽이나 위 열과 크기를 비교해서 합친다.

 

string 입출력에 익숙해지기 위해 string 헤더를 사용했다.

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

FILE* in = fopen("input.txt", "r");

string a;
string b;
int dp[1001][1001];

void get_matrix(int i, int j) {
	if (a[i] == b[j])
	{
		if (i == 0)
		{
			dp[i][j] = 1;
		}
		else if(j == 0)
		{
			dp[i][j] = 1;
		}
		else
		{
			int tmp = max(dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] = max(tmp, dp[i - 1][j - 1] + 1);
		}
	}
	else
	{
		if (i == 0)
		{
			if (j == 0)
				dp[i][j] = 0;
			else
				dp[i][j] = dp[i][j - 1];
		}
		else if (j == 0)
		{
			dp[i][j] = dp[i - 1][j];
		}
		else
		{
			int tmp = max(dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] = tmp;
		}
	}

}

int main() {
	cin >> a;
	cin >> b;
	for (int i = 0; i < a.length(); i++)
		for (int j = 0; j < b.length(); j++)
			get_matrix(i, j);
	/*for (int i = 0; i < a.length(); i++)
	{
		for (int j = 0; j < b.length(); j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	cout << dp[a.length() - 1][b.length() - 1];
	return 0;
}