baekjoon. LCS

문제

풀이

dp는 나름 익숙해져 간다고 생각하면서 맞딱들인 문제..

이때까지 맛보기식 dp만 풀어놓고 자신감을 늘려가고 있다는걸 깨달았다

친구가 기본적으로 dp는 2차원 배열로 푼다고 하길래 한참 멀었다는 생각을 하게 되었다

문자를 하나씩 늘려가면서 dp배열을 채워나가면서 풀면된다

간단하게 설명하자면

ACAYKP/ CAPCAK	A	AC	ACA	ACAY	ACAYK	ACAYKP
C	0	1	1	1	1	1

A와 C를 비교 하면 LCS는 0이라 0을, AC의 'C'와 C는 1을 채워주고 비교할 문자열이 C하나이기 때문에 그 뒤도 전부 1로 채운다

ACAYKP/ CAPCAK	A	AC	ACA	ACAY	ACAYK	ACAYKP
C	0	1	1	1	1	1
CA	1	1	2	2	2	2

문제는 여기서부터인데 AC'A'와 C'A'가 겹친다 그럼 우리는 카운트를 늘려주어야하는데 AC와 CA에서 1을 더해서 2를 적어주는 것이 아니다

윗줄에서 AC와 C의 비교값에서 +1을 해주어야한다 그것이 dp니까.

그렇게 배열을 채워나가다 보면

ACAYKP/ CAPCAK	A	AC	ACA	ACAY	ACAYK	ACAYKP
C	0	1	1	1	1	1
CA	1	1	2	2	2	2
CAP	1	1	2	2	2	3
CAPC	1	2	2	2	2	3
CAPCA	1	2	3	3	3	3
CAPCAK	1	2	3	3	4	4

이런 2차원 배열이 완성된다

실제로 2차원 배열에선 점화를 위한 0으로 초기화된 배열이 가로세로 한줄씩필요하기때문에 7x7의 배열을 생성해줘야한다

코드

    const input =`ACAYKP
CAPCAK`.split('\n');
  // const input = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n');
  const cache = Array(input[0].length+1).fill(0).map(()=>Array(input[1].length+1).fill().map(()=>0));

  for(let i=0; i<input[0].length;i++){
      for (let j=0; j<input[1].length;j++) {
          if (input[0][i] === input[1][j]) cache[i+1][j+1] = cache[i][j]+1;
          else cache[i+1][j+1] = Math.max(cache[i+1][j],cache[i][j+1]);
      }
  }

  console.log(cache[input[0].length][input[1].length]);