9251번 LCS

dp문제는 항상 어렵다. 이전의 값을 재사용해야하는데, 이 문제는 어떤방식으로 재사용 할지 도저히 생각이 안났다.
답지를 봤다. 쉬운데 어렵다. 그래서 유튜브쌤을 활용!

https://www.youtube.com/watch?v=P-mMvhfJhu8

이그림이 핵심임.

여기서 자세하게 설명해주신다. 원론은 이러하다.

• str1의 i번째 문자열 = str2의 j번째 문자열 이면, str1의 i-1번째 문자열과 j-1번째 문자열까지 최장부분수열의 값 + 1 => Xi = Yj 면 Xi-1 = Yj-1
  이건 알겠다.
• str1의 i번째 문자열 != str2의 j번째 문자열이면, 이전글자까지의 최댓값중 Xi-1 Yj와 Xi Yj-1을 비교해서 최댓값을 택하면 된다. => Xi != Yj면 max(Xi-1 Yj, Xi Yj-1)
  이걸 아직 잘 모르겠다. (ACA와 CAP는 다르다. 따라서 ACA,CA 와 AC,CAP중 더 긴것을 택하면 됨?)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [a, b] = input;
const str1 = " " + a;
const str2 = " " + b;

const d = Array.from({ length: 1002 }, () => Array(1002).fill(0));
for (let i = 1; i <= str1.length; i++) {
  for (let j = 1; j <= str2.length; j++) {
    if (str1[i] === str2[j]) {
      d[i][j] = d[i - 1][j - 1] + 1;
    } else {
      d[i][j] = Math.max(d[i][j - 1], d[i - 1][j]);
    }
  }
}

console.log(d[a.length][b.length]);

코드는 무지 간단하다. 하지만 발상이 어렵다. 이게 dp문제의 핵심이다. 점화식을 유도하는 과정이 순탄치 않다...
대부분 표를 그려서 하던데, 다음부턴 표를 그려서 풀어봐야지...