[백준 9251번] LCS - JAVA

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

9251번: LCS

풀이

사용한 알고리즘 : DP, LCS(Longest Common Subsequence)

 

풀이전략

1. 주어진 두 문자열 길이에 맞게 이차원 배열을 선언한다.

   int d[][] = new d[두번째문자열.length()+1][첫번째문자열.length()+1]

2. 문자열에서 동일한 문자가 있을 경우 D[i+1][j+1]=D[i][j]+1

   문자열에서 동일한 문자가 없을 경우 D[i+1][j+1]=Math.max(D[i+1][j],D[i][j+1])

   이라는 패턴을 찾을 수 있으므로 DP를 사용하여 바텀업해 이차원 배열을 채운다.

   ex) d[4][2]는 첫 번째 문자열 중 {A,C}와 두 번째 문자열{CAPC} 사이의 LCS 값이 저장된다.

3. 이차원 배열을 채워가면서 가장 큰 값을 저장해뒀다가 출력한다.

 

제출코드

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

public class Main {
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1=br.readLine();
        String str2=br.readLine();

        int d[][] = new int[str2.length()+1][str1.length()+1];
        int maxVal=0;

        for(int i=0;i<str2.length();++i){
            for(int j=0;j<str1.length();++j){
                if(str2.charAt(i)==str1.charAt(j)){
                    d[i+1][j+1]=d[i][j]+1;
                }
                else{
                    d[i+1][j+1]=Math.max(d[i][j+1],d[i+1][j]);
                }
                maxVal=(maxVal<d[i+1][j+1])?d[i+1][j+1]:maxVal;
            }
        }
        System.out.println(maxVal);
    }
}