[백준][LCS] 9251 LCS NodeJs 구현

목차

 

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

문제

 

문제 구현 전 읽으면 좋은 것

친절하게 설명이 되어있다..

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let a = input[0].trim().split("");
a.unshift(0);
let b = input[1].trim().split("");
b.unshift(0);

let dp = Array.from(Array(1001), () => Array(1001).fill(0));


for (let i = 0; i < a.length; i++) {
  for (let j = 0; j < b.length; j++) {
    if (i === 0 || j === 0) {
      dp[i][j] = 0;
      continue;
    }
    if (a[i] === b[j]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
}
console.log(dp[a.length - 1][b.length - 1]);