9251 : LCS (Dynamic Programming) [C,C++]

LCS 문제이다..!!

LCS 문제를 처음 풀어봤는데 DP 기본 문제이지만 이걸 어떻게 DP로 풀어라는 생각에

 DP로는 생각을 못하고 3시간동안 풀다가 계속 오답이 나서 

LCS 알고리즘을 검색해보니 DP로 간단히 풀 수 있었다. 와 이게 이렇게 되네?

처음 문제 풀이 

DP를 이용하지 않음(i와 j의 값을 계속 이동시켜 품) => 정답은 맞지만 시간이 초과됨.

두 번째 생각

스택을 이용해보자.

(i와 j의 값들을 vector<int> 템플릿 스택에 push 후

j가 max_size에 도달하면 pop하여 j의 값을 변경하는 식으로 진행.)

=> 정답은 맞지만 런타임 에러가 뜸.

결국 검색 후,

LCS 알고리즘 사용.

DP를 사용함으로써 메모리는 처음이나 두 번째보다는 많이 잡아먹지만

시간이 무척 빨라짐. 

LCS 알고리즘의 규칙 3가지

하나. 각 행,열이 0번째라면 그 값은 0이다.

둘. 비교하는 글자가 서로 같다면 그 값은 행렬의 ↖에 있는 값의 +1이다.

셋. 비교하는 글자가 서로 같지 않다면 그 값은 왼쪽 값이나 위의 값 중 더 큰 값이다.

if (i == 0 || j == 0)
 this->Array[i][j] = 0;
else
{
 if (A[i - 1] == B[j - 1])
  this->Array[i][j] = this->Array[i - 1][j - 1] + 1;
 else
 {
  this->Array[i][j] = this->Array[i - 1][j] < this->Array[i][j - 1] ? this->Array[i][j - 1] : this->Array[i - 1][j];
 }
}

<핵심 코드>

*Source of the problem = https://www.acmicpc.net/problem/2239

*문제 출처 : BAEKJOON ONLINE JUDGE