[백준] 9251 LCS - Java

 

 

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

LCS 알고리즘을 알면 dp를 이용해 쉽게 풀 수 있다.. 모르면 못풀고 알면 푸는 그런 문제..

 

import java.io.*;
import java.util.*;
 
public class Main {

    static String str1;
    static String str2;

    static int[][] dp;

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

        dp = new int[str1.length()][str2.length()];

        for(int i=0; i<str1.length(); i++){
            for(int j=0; j<str2.length(); j++){
                dp[i][j] = -1;
            }
        }

        System.out.println(LCS(str1.length() - 1, str2.length() - 1));
        
    }

    static int LCS(int a, int b){
        
        if(a == -1 || b == -1){
            return 0;
        }

        if(dp[a][b] == -1){            

            if(str1.charAt(a) == str2.charAt(b)){
                dp[a][b] = LCS(a - 1, b - 1) + 1;
            }else{
                dp[a][b] = Math.max(LCS(a -1, b), LCS(a, b-1));
            }
        }

        return dp[a][b];
        
    }
}