백준 LCS 9251 java

문제링크

문제 접근

• 공통 부분 문자열 문제와 다른 점은 문자열이 연속이지 않아도 된다는 것
• 비슷하게 2차원 배열을 만들어서 DP로 접근
• 근데 LCS[i-1][j-1]만 비교하는 것이 아닌 LCS[i-1][j], LCS[i][j-1]도 비교

코드

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

public class baek_9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int answer = 0;
        int N = A.length();
        int M = B.length();
        int[][] LCS = new int[N+1][M+1];
        for(int i=1;i<=N;i++){
            char A_now = A.charAt(i-1);
            for(int j=1;j<=M;j++){
                char B_now = B.charAt(j-1);
                if(A_now == B_now) LCS[i][j] = LCS[i-1][j-1] + 1;
                else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);

                answer = Math.max(answer, LCS[i][j]);
            }
        }
        System.out.print(answer);
    }
}

결과

정리

• 두 문자열의 공통 부분 문자열, 공통 부분 수열까지 클리어...