백준 알고리즘 9251번: LCS(Python)

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

9251번: LCS

---

문제 해결을 위한 과정

이 문제는 행렬을 이용하여 기준이 되는 문자열과 다른 문자열을 한 글자씩 증가해가며 LCS를 구하는 문제였습니다. 행렬을 그린 후 하나씩 작성해 나가다 보면 규칙을 찾을 수 있습니다.

아래의 표에서 빨간색으로 칠한 3행 4열을 보시면 ACAYK에 CAPC의 LCS가 2라는 것을 알 수 있습니다.

이는 ACAYK CAPC 이기 때문입니다. 같은 원리로 5행4열을 보시면 ACAYK에 CAPCAK의 LCS가 4인 것을 알 수 있는데 이는 ACAYK CAPCAK이기 때문입니다. 

다시 위의 표를 보시면 규칙을 찾을 수 있는데 바로 위의 행이 그대로 아래의 행으로 내려온 후 비교해나가다가 같은 글자를 만나면 좌측 + 1이 된다는 것입니다. 다른 글자의 경우 max(좌, 상)이 들어가는 것을 확인할 수 있습니다. 

다른 글자의 경우 max(좌, 상)이 이해가 안 될 수 있어서 다른 예시를 첨부하면 다음과 같습니다.

2행4열을 보면 다음과 같이 P와 T가 다르기 때문에 max(1, 2)인 2가 들어간 것을 확인할 수 있습니다. 따라서 이를 코드로 옮기면 됩니다.

---

소스코드 - python

(코드 작성의 편의를 위해 행과 열을 하니씩 추가 하였습니다.)

word1 = input()
word2 = input()
 
n = len(word1)
m = len(word2)
 
data = [[0] * (m+1) for _ in range(n+1)]
 
for i in range(1, n+1):
  for j in range(1, m+1):
    data[i][j] = data[i-1][j]
 
  for j in range(1, m+1):
    if word1[i-1] == word2[j-1]:
      data[i][j] = data[i-1][j-1] + 1
    else:
      data[i][j] = max(data[i][j-1], data[i-1][j])
 
print(data[n][m])

---

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
int main(void) {
  char word1[MAX];
  char word2[MAX];
  scanf("%s", word1);
  scanf("%s", word2);
 
  int n = strlen(word1);
  int m = strlen(word2);
 
  int data[MAX][MAX] = {0};
 
  for (int i = 1; i < n+1; i++) {
    for (int j = 1; j < m+1; j++) {
      data[i][j] = data[i-1][j];
    }
 
    for (int j = 1; j < m+1; j++) {
      if (word1[i-1] == word2[j-1])
        data[i][j] = data[i-1][j-1] + 1;
 
      else
        data[i][j] = max(data[i][j-1], data[i-1][j]);
    }
  }
 
  printf("%d\n", data[n][m]);
  return 0;
}