[백준 - 9251] LCS

백준 9251 번 Node.js 문제풀이

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

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.


예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4

LCS 풀이 표

내 코드

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


const str1 = input[0].split('');
const str2 = input[1].split('');
const len = str1.length;
const len2 = str2.length;
// 2차원 배열 생성

// 0으로 초기화
const DP = Array.from(Array(2000), () => Array());

// 모든 행, 열 0으로 초기화
for(let i = 0; i <= len; i++) {
  for(let j = 0; j <= len2; j++) {
    DP[i][j] = 0 
  }
}


for(let i = 1; i <= len; i++) {
  for(let j = 1; j <= len2; j++) {   
    // i - 1, j - 1이 같은 경우,
    if(str1[i - 1] === str2[j - 1]) {
      // 대각선 왼쪽 위의 값에서 + 1
      DP[i][j] = DP[i - 1][j - 1] + 1
    } else {
      // 아니면, [i][j - 1], [i - 1][j]의 값에서 큰 값 가져오기
      DP[i][j] = Math.max(DP[i][j - 1], DP[i - 1][j])
    }
  }
}

console.log(DP[len][len2])