[알고리즘] Java / 백준 / 공통 부분 문자열 / 5582

[알고리즘] Java / 백준 / 공통 부분 문자열 / 5582

문제

문제 링크

접근 방식

첫 번째 문자열의 길이와 두 번째 문자열의 길이를 행 열로 하는 2차원 배열을 만들고 각 칸에서 첫 번째 문자열의 문자와 두 번째 문자열의 문자를 비교하여 같을 때 이전 행, 이전 열의 값에 1을 더한 값을 현재 값에 저장한다

if str.char(i) == str.char(j) => dp[i][j] = dp[i-1][j-1]

이 식의 의미는 문자열 1과 2를 비교하면서 문자열 1의 i번째 문자와 문자열 2의 j번째 문자가 같을 때 각각 문자열의 바로 이전 문자까지의 공통부분 문자열 길이에 1을 더해 현재에 저장한다는 뜻이다

코드

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

public class Main_5582 {
    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()][str2.length()];
    	
    	int max = 0;
    	for(int i=1;i<str1.length();i++) {
    		for(int j=1;j<str2.length();j++) {
    			if(str1.charAt(i) == str2.charAt(j)) {
    				dp[i][j] = dp[i-1][j-1] + 1;
    				max = Math.max(dp[i][j], max);
    			}
    		}
    	}
    	
    	System.out.println(max);
    }
}