BOJ#9251 LCS

BOJ#9251 LCS

* 문제

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

LCS(Longest Common Subsequence, 최장 공통 부분 수열)

* 풀이

2개의 문자열의 공통 부분 문자열의 길이를 구하는 문제입니다.

ex) abcd, bd 일 때 -> 공통 부분 문자열은 bd이고 길이는 2

dp 정의는 아래와 같고

dp[i][j] : s_1, ... , s_i와 t_1, ... , t_j에 대한 LCS의 길이

s_1, ... , s_i+1와 t_1, ... , t_j+1에 대해서

1) s_i+1 = t_j+1 이라면

dp[i+1][j+1] = dp[i][j] + 1

2) s_i+1 != t_j+1 이라면

dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%239251_LCS/src

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

/**
 * BOJ#9251 Longest Common Subsequence
 * https://www.acmicpc.net/problem/9251
 */

public class Main {

    static int[][] dp = new int[1001][1001]; // i번째 글자가 마지막 글자인 LCS의 length

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

        StringBuffer S;
        StringBuffer T;
        int sLength, tLength;

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

        S = new StringBuffer(br.readLine());
        T = new StringBuffer(br.readLine());

        sLength = S.length();
        tLength = T.length();

        for (int i = 0; i < sLength; i++) {

            for (int j = 0; j < tLength; j++) {

                if (S.charAt(i) == T.charAt(j)) {

                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {

                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }

        System.out.println(dp[sLength][tLength]);

    } // main
}