[백준 9251] LCS

 

 

수열은 자주 나오는 DP 문제이다.

이곳에서 LCS에 대한 설명을 확인할 수 있다.

위에서 나온 설명대로 점화식을 구현하여 풀었다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String a = " " + sc.next();
        String b = " " + sc.next();
        int dp[][] = new int[b.length()][a.length()];
        
        for(int i=1; i<b.length(); i++) {
            for(int j=1; j<a.length(); j++) {
                if(b.charAt(i) == a.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        System.out.println(dp[b.length()-1][a.length()-1]);
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}