🎲 백준 9251번 LCS

백준 9251번

📌 LCS참고 자료 : LCS 알고리즘에 대해 아주 자세히 나와있다.

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const A = input.shift().split("");
const B = input.shift().split("");

const dp = Array.from(new Array(A.length + 1), () =>
  new Array(B.length + 1).fill(0)
);

for (let a = 1; a < A.length + 1; a++) {
  for (let b = 1; b < B.length + 1; b++) {
    if (A[a - 1] === B[b - 1]) {
      dp[a][b] = dp[a - 1][b - 1]+1;
    } else {
      dp[a][b] = Math.max(dp[a - 1][b], dp[a][b - 1]);
    }
  }
}

console.log(dp[A.length][B.length]);