[백준] LCS

[백준] LCS - Java

너지살 2022. 5. 9. 17:45

문제출저 :

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

9251번: LCS

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

www.acmicpc.net

소스코드

package studyGroup.april.april20;


/*

dp문제



*/

import java.util.*;
import java.lang.*;
import java.io.*;

public class LCS9251 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int n = s1.length();
        int m = s2.length();

        int[][] board = new int[n+1][m+1];

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(s1.charAt(i) == s2.charAt(j))
                {
                    board[i+1][j+1] = board[i][j] + 1;
                }
                else
                {
                    board[i + 1][j + 1] = Math.max(board[i + 1][j], board[i][j + 1]);
                }
            }
        }

        System.out.println(board[n][m]);






    }
}