백준 9251 - LCS

문제

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

리뷰

이 문제는 주어진 두 문자열에서 가장 긴 공통 문자열의 길이를 도출하는 문제이다.
우선 주어진 두 문자열의 길이를 바탕으로 메모이제이션을 실현할 배열 dp 를
선언하였다. dp[i][j]는 문자열1의 i번째까지 문자열과 문자열2의 j번쨰까지
문자열을 비교하였을떄 가장 긴 부분 문자열의 길이를 의미한다. 이와 같이 정의하면
아래와 같은 점화식이 성립하며 이를 그대로 코드로 옮기면 된다.

로직의 시간 복잡도는 주어진 문자열의 길이를 각각 $N$, $M$이라 했을때 $O(NM)$
으로 수렴하고, 최악의 경우 $1000^2$ 번 연산을 수행하기 때문에 시간 제한 조건이
0.1초를 무난히 통과한다.

코드

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();

        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 1; i < dp.length; i++)
            for (int j = 1; j < dp[i].length; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    continue;
                }

                boolean eq = str1.charAt(i - 1) == str2.charAt(j - 1);

                if (eq)
                    dp[i][j] = Math.max(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.print(dp[str1.length()][str2.length()]);
        in.close();
    }
}

결과

참고
해당 문제와 관련하여 정말 좋은 설명글이 있어 공유합니다.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring