[백준] 5582 공통 부분 문자열 - DP JAVA

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

코드설명

DP 문제입니다. 

 

이 문제에서 DP = new int[str1.length()][str2.length()] 는 가장 긴 공통 부분 문자열의 개수를 의미합니다.

 

아래의 예시와 함께 살펴봅니다.

입력
ABRACADABRA
ECADADABRBCRDARA

출력
5

1. ABRACADABRA 를 먼저 str2의 시작인 E로 확인합니다. 같은 숫자가 하나도 없으므로 DP[0][1~str1.length()] = 0 입니다.

2. ABRACADABRA 를 이제 str2의 두번째 값인 C로 확인합니다. str1.charAt(5)에서 "C"를 발견했습니다. "C"의 이전 숫자인 "E"와 연관되었는지 확인하기 위해 DP[1][5] = DP[0][4] + 1 을 처리합니다. DP[0][4]를 체크하는 이유는 해당 값을 통해 "C"이전 숫자와 연결되었는지 확인하기 위함입니다.

3. 1~2번의 로직을 계속해서 을 반복합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[][] DP;
	public static String str1, str2;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str1 = st.nextToken();
    	
    	st = new StringTokenizer(br.readLine());
    	str2 = st.nextToken();
    	DP = new int[str1.length()][str2.length()];
    	
    	for(int i=0; i<str1.length(); i++) {
    		for(int j=0; j<str2.length(); j++) {
    			
    			if(str1.charAt(i) == str2.charAt(j)) {
    				if( i - 1 < 0 || j - 1 < 0) {
    					DP[i][j] = 1;	
    				}
    				else {
    					DP[i][j] = DP[i-1][j-1] + 1;
    				}
    				answer = Math.max(answer,  DP[i][j]);
    			}
    		}
    	}
    	System.out.println(answer);
	}

}