백준 9251번 - LCS

문제

백준 9251번 - LCS

아이디어

• 대표 문자열 DP 문제인 LCS 문제다.
• 각 문자열을 축으로 하는 2차원 DP 배열을 생성한다.
• 특정 위치의 두 문자의 값이 같으면 (왼쪽 대각선 값 + 1)을 현재 위치에 저장한다.
• 값이 다르면 왼쪽 값과 위쪽 값 중 큰 값을 선택해 저장한다.

예상 시간 복잡도

• 두 문자열을 이중 반복문으로 탐색한다.
• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_9251 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();

        int lenA = A.length;
        int lenB = B.length;

        int[][] dp = new int[lenA + 1][lenB + 1];

        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {

                if (A[i - 1] == B[j - 1]) { //두 문자가 같으면 왼쪽 대각선 + 1 저장
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                } else {                    //두 문자가 다르면 왼쪽과 위쪽 값 중 큰 값 저장
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[lenA][lenB]);
    }
}