[백준] 9251번 LCS (gold 5

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));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        String a=br.readLine();
        String b=br.readLine();

        int[][] map=new int[b.length()][a.length()];

        for(int i=0; i<b.length(); i++){
            for(int j=0; j<a.length(); j++){
                if(a.charAt(j)==b.charAt(i)){
                    map[i][j]=1;
                }
            }
        }
        int answer=0;
        int max=0;
        for(int i=b.length()-1; i>=1; i--){
            max=0;
            for(int j=a.length()-1; j>=0; j--){
                if(map[i-1][j]==0){
                    map[i-1][j]=Math.max(max, map[i][j]);
                    max=Math.max(max,map[i][j]);
                }
                else{
                    map[i-1][j]+=max;
                    max=Math.max(max,map[i][j]);
                }
            }
        }

        for(int i=0; i<a.length(); i++){
            answer=Math.max(map[0][i],answer);
        }
        bw.write(answer+"");
        bw.flush();
    }
}

//문자열 두개를 배열로 만든다. 한 비교당할 문자를 열 칸에 배열하고.
//비교할 문자를 행으로 하여, 각 알파벳이 일치하는 칸에 1로 표기를 한다.
//  a c a y k p
//c 0 1 0 0 0 0
//a 1 0 1 0 0 0
//p 0 0 0 0 0 1
//c 0 1 0 0 0 0
//a 1 0 1 0 0 0
//k 0 0 0 0 1 0

//위와 같은 형식의 배열이 만들어진다.
//맨오른쪽 하단부터 시작하여 비교하는데.
//0이 아닌경우는 동일한 문자가 그 갯수 만큼 들어있다.
//만약 0이 아닌 배열의 바로 위 행이 0이면 그 위에서는 이 행을 이용해야 하는데 이용을 못하므로,
//0이 아닌 배열 위에 max값과, 배열의 값중 큰 것을 넣는다.
//이때 max는 비교할 문자의 n번째에서 겹치는 문자열 중 가장 큰 값이다.
// 0 1 0 2 0 1 의 경우에서 처음에는 바로 위 배열에 1을 추가하면 되지만,
//2의 동일 배열 수가 있으면 2를 넣어야 하므로 비교를 하는 것이다.
//0이 아닌 배열 위의 행 배열이 0이 아니면 이 값에 현재 자리번째에서 최대 배열 수 max를 더한 값을 넣는다.
//열 번호에서 i번째의 바로 위 행 i번째에는 바로 아래 i번째 값을 더할 수는 없다. 동일 한 위치이므로,
//동일한 자리번의 문자를 한번 더 넣는 행위이기 때문이다.
//따라서 이런 일련의 과정을 거치고, max값을 비교하여, 
//i번째에서 max가 바뀌면서 그 위의 값에 max가 그대로 더해지는 것을 방지한다.
//위의 과정을 마치면 예제의 배열은

//4 3 2 1 1 1
//3 3 2 1 1 1
//2 3 2 1 1 0
//2 1 2 1 1 0
//0 0 0 0 1 0
//이 나오므로,
//비교하여 가장 큰 길이를 뽑으면 된다.