[알고리즘] Java / 백준 / LCS / 9251

[알고리즘] Java / 백준 / LCS / 9251

문제

문제 링크

접근 방식

LCS 알고리즘 공식은 다음과 같다

이미지 출처

1. 문자열 1과 2 각각 길이+1을 행과 열로 하는 2차원 배열을 만든다
2. 0행과 0열의 값은 0이다
3. 1행 1열부터 두 문자열의 문자를 비교한다
4. 각 문자가 같으면 현재 값에, 현재 위치에서 행 -1 , 열 -1 의 값에 1을 더한 값을 넣는다
5. 각 문자가 다르면 현재 값에, 현재 위치 바로 이전 행 값과 이전 열 값 중 큰 값을 넣는다

4번째 줄의 의미는 문자열1의 n번째 문자와 문자열2의 m번째 문자가 같다면 문자열1의 n-1번째, 문자열2의 m-1번째까지의 가장 긴 공통 부분 수열의 길이에 1을 추가로 더한다는 뜻이다

5번째 줄의 의미는 현재 문자열1의 n번째 문자와 문자열2의 m번째 문자가 다르기 때문에 지금까지의 가장 긴 공통 부분수열 길이 중 큰 값을 현재 값에 넣는다는 뜻이다

코드

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

public class Main_9251_baekjoon {

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

}