[JAVA]백준5582번 공통 부문 문자열

문제는 다음과 같다.

오늘은 백준5582번 공통 부문 문자열 문제를 풀어보도록 하자. 위 문제는 Long Common Subsequence이 아닌 Long Common Substring문제이다. 둘 다 LCS이고 DP로 풀이가 가능하다.

기본적인 LCS문제이고 가장 긴 공통 문장을 찾는 로직은 다음과 같다.

1. Long Common Subsequence와는 다르게 누적이라는 개념이 아니라 갱신의 느낌이다.
2. 만일 문자가 같다면 대각선 위의 값에 1을 더해주는, 즉 이어나간다는 느낌은 Long Common Subsequence와 같다.
3. 하지만 answer을 갱신해줄 때는 다르다. 만일 ABC와 AC가 있다고 하자. Long Common Subsequence 같은 경우엔 AC로 답은 2가 되겠지만 위 Substring은 A or C로 답은 1이된다.
4. 왜냐하면 Substring은 dp배열의 값이 0->1이 될 때 answer가 갱신이 되고 Subsequence는 마지막의 배열 값을 보기 때문에 누적된 2가 정답이 도니다.

                                     [코드]
package BaekJoon;

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

public class Main_5582 {
    static int dp[][];
    static int answer = 0;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s_1 = br.readLine();
        String s_2 = br.readLine();

        dp = new int[s_1.length()+1][s_2.length()+1];

        for(int i=1;i<=s_1.length();i++){
            for(int j=1;j<=s_2.length();j++){
                if(s_1.charAt(i-1) == s_2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if(answer < dp[i][j]){
                        answer = dp[i][j];
                    }
                }
            }
        }
        System.out.println(answer);
    }
}