[백준 코딩테스트] 9251번 LCS

풀이

이 문제는 동적계획법을 사용해 접근해야 한다.
두 문자열의 공통 문자들을 하나씩 누적시키면서 값을 증가시켜야 한다.

내가 한번에 접근하지 못한 이유 중 하나가 2차원 배열로 만들어서 접근해야했었다는 점이다.
두 문자열 모두 방문해야 하기 때문에 2차원 배열을 생성했어야 했는데 단순 loop 문으로 접근했기 때문에 초반에 방향을 잡는데 오래 걸렸던 것 같다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static char[] a;
    static char[] b;
    static Integer[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        a = br.readLine().toCharArray();
        b = br.readLine().toCharArray();
        dp = new Integer[a.length][b.length];

        System.out.println(lcs(a.length-1, b.length-1)); 
    }

    static int lcs(int x, int y){
        if(x==-1 || y==-1) return 0;
        if(dp[x][y] == null){
            dp[x][y] = 0;
            if(a[x] == b[y]) dp[x][y] = lcs(x-1, y-1)+1; // 부분 수열 찾음 -> +1, 값을 누적시키며 LCS 값 증가시킴
            else dp[x][y] = Math.max(lcs(x, y-1), lcs(x-1, y)); 
        }

        return dp[x][y];
    }
}