🔍 Problem

9251 LCS

---

📃 Input&Output

---

📒 해결 과정

1️⃣ 각 문자열을 한칸씩 늘려 부분 수열이 있는지 비교한다. 그리고 부분수열 길이의 최대 길이를 dp에 저장한다.

2️⃣ 다음 2가지 경우를 생각하며 dp를 채운다.

가. 만약 비교하고 있는 수열의 맨 끝 글자가 같으면 이전 수열들의 부분수열 최대값에 +1을 한다.

$dp[i][j] =dp[i-1][j-1]+1$

왜냐하면 이전 각 마지막 문자를 뺀 수열의 부분수열 길이 최대값에서 +1을 해줘야하기 때문이다.

나. (가)에 해당하지 않는다면, DP는 각 수열의 기준의 부분수열 길이 최대값 중 더 큰값과 같다.

$dp[i][j] = max(dp[i-1][j], dp[i][j-1])$

---

❗트러블슈팅

1. $dp[i][j] =dp[i-1][j]+1$가 아닌 이유

이 문제는 각 문자열 끝단을 서로 추가하며 비교하고 있기 때문이다.
따라서 $dp[i][j] =dp[i-1][j-1]+1$ 이다.

---

💻 Code

// const path = 'input.txt'
const path = '/dev/stdin'


const input = require('fs')
    .readFileSync(path)
    .toString()
    .trim()
    .split('\n')


const dp = Array.from({ length: input[0].length + 1 }, () => 
    Array(input[1].length + 1).fill(0))




let w1,w2
for (let i = 1; i < input[0].length + 1; i++) {
    w1 = input[0][i - 1]
    for (let j = 1; j < input[1].length + 1; j++) {
        w2 = input[1][j - 1]

        if (w1===w2){
            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[input[0].length][input[1].length])

---

🤔 느낀점

어렵다.

---

📝 출처

임우찬님 블로그