링크

9251 LCS

문제

풀이

이 문제 생각보다 어려웠다.
일단 내풀이는 이렇다

처음에 같은 문자가 있을때 +1을 하는것이 바로 왼쪽에 있는 값 + 1하는줄 알았는데 계속 틀려서 블로그를 찾아봤다
대각선 왼쪽 위에 있는 값을 +1 해야한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

        String[] str1 = br.readLine().split("");
        String[] str2 = br.readLine().split("");
        int[][] dp = new int[str1.length + 1][str2.length + 1];

        for(int i=0;i<str1.length;i++){
            String currentWord = str1[i];

            for(int j=0;j<str2.length;j++){
                if(currentWord.equals(str2[j])){
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else{
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }


//        for(int i=0;i<dp.length;i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }

        int max = 0;

        for(int i=0;i<dp[0].length;i++){
            max = Math.max(max, dp[dp.length - 1][i]);
        }

        System.out.println(Math.min(max, Math.min(str1.length, str2.length)));
    }


}