[백준] 9251 LCS (JAVA)

풀이

dp를 이용하여 푸는 문제이다 주의해야할점은 dp배열이 2차원이라는 것이다. 나는 아래의 블로그를 참고하였다.

 

https://st-lab.tistory.com/139

[백준] 9251번 : LCS - JAVA [자바]

 

코드

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

class Main {

    static char[] case1, case2;
    static Integer[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        case1 = br.readLine().toCharArray();
        case2 = br.readLine().toCharArray();

        dp = new Integer[case1.length][case2.length];

        System.out.println(LCS(case1.length - 1, case2.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(case1[x] == case2[y]) dp[x][y] = LCS(x-1, y-1) + 1;
            else dp[x][y] = Math.max(LCS(x, y-1), LCS(x-1, y));
        }

        return dp[x][y];
    }
}