Baekjoon9251-LCS

백준 사이트 9251 - LCS 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DB문제입니다.
LCS라는 따로 알고리즘이 존재할 정도로 유명한 문제입니다.
백준에서는 Gold5난이도를 책정하고 있습니다.

---

4. 생각한 것들

• LCS 들어는 봤지만 직접 짜본 적이 없어서 위키백과에서 개념만 이해하고 코드는 직접 짰습니다.
  • 문자열의 길이가 큰 것이 먼저 들어올 경우 등 예외를 생각했으나 코드를 짜고나니 길이와는 상관이 없었습니다.
  • 위키백과에서 이해를 하고나니 코드를 짜는건 어렵지 않았습니다.

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

---

5. code

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

using namespace std;

int const MAX = 1001;
int LCS[MAX][MAX] = { 0, };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string input1, input2;
	cin >> input1 >> input2;

	int result = 0;

	//LCS만들기
	for (int i = 1; i < input1.size() + 1; ++i)
	{
		for (int j = 1; j < input2.size() + 1; ++j)
		{
			if (input1[i - 1] == input2[j - 1])
			{
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			}
			else
			{
				LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
			}
			result = max(result, LCS[i][j]);
		}
	}
	cout << result;

	return 0;
}
/*
위키피디아 예제
XMJYAUZ
MZJAWXU

*/

---

6. 후기

처음에 틀려서 질문을 보다가 많은 사람들이 LCS배열을 char형으로 작성했다.
당장 문자열의 길이가 MAX 1천이 되는데 char형으로 왜 작성했을 지 의문이 들었다.