[BOJ][DP] 9251. LCS (java)

✏️ 문제

문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

🔢 알고리즘

 

#DP  #LCS

 

 

🤯 풀이 방법

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

참고했당..

어떻게 떠올리는거지?

 

 

👾 구현 코드 (자바)

import java.util.Scanner;

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

        String s1 = sc.nextLine();
        String s2 = sc.nextLine();

        int I = s1.length();
        int J = s2.length();

        int[][] cnt = new int[I + 1][J + 1];

        for (int i = 1; i <= I; i++) {
            for (int j = 1; j <= J; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    cnt[i][j] = cnt[i-1][j-1] + 1;
                } else {
                    cnt[i][j] = Math.max(cnt[i-1][j], cnt[i][j-1]);
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= I; i++) {
            for (int j = 1; j <= J; j++) {
                ans = Math.max(ans, cnt[i][j]);
            }
        }

        System.out.println(ans);

    }
}