[99클럽 5기 코테 스터디 TIL 23일차] LCS (feat. 동적계획법)

1) 문제

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

 

 

2) 해결

코드 해석

1. 입력 처리:
   • Scanner를 사용하여 두 개의 문자열을 입력받음
2. DP 테이블 초기화:
   • dp[i][j]는 str1[0...i-1]과 str2[0...j-1]의 LCS 길이를 저장함
   • 따라서 dp 배열의 크기는 (len1+1) x (len2+1)로 설정함
3. DP 점화식 적용:
   • 두 문자열의 각 문자를 비교하면서 LCS를 구함
   • str1[i-1] == str2[j-1]이면, dp[i][j] = dp[i-1][j-1] + 1
   • 다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. 결과 출력:
   • dp[len1][len2]에 LCS의 길이가 저장되므로 이를 출력함

이 코드는 시간 복잡도가 O(N×M)O(N \times M)O(N×M)로, 충분히 빠르게 동작함

import java.util.Scanner;

public class LCS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        sc.close();
        
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 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[len1][len2]);
    }
}