[백준] 9251번 : LCS[Java]

#풀이

import java.io.*;
import java.util.*;



public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        int max = 0;
        for(int i = 1; i<str1.length()+1; i++){
            for(int k = 1; k<str2.length()+1; k++){
                if(str1.charAt(i-1)==str2.charAt(k-1)){
                    dp[i][k]=dp[i-1][k-1]+1;
                }
                else dp[i][k] = Math.max(dp[i-1][k],dp[i][k-1]);
                if(max<dp[i][k])max = dp[i][k];
            }
        }
        System.out.println(max);


    }
}

#성능

#정리

처음에 그리디로 접근했다가 틀렸다.

알고리즘 분류를 보고 DP로 접근했다.

점화식은 다음과 같다.

비교하는 문자가 같은경우 -> dp[i][j] = dp[i-1][j-1]+1

비교하는 문자가 다른경우 -> dp[i][j] = max(dp[i-1][j],dp[i][j-1])

시간이 지나고 다시 풀어봐야 할 것 같다.