[백준알고리즘 - 9251] LCS(Java)

(1) 문제

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

---

(2) 입력

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

---

(3) 출력

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

---

(4) 예제 입력 및 출력

---

(5) 코드

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

public class LCS {
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); 
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String firstString = bufferedReader.readLine();
        String secondString = bufferedReader.readLine();

        int[][] LCS = new int[firstString.length() + 1][secondString.length() + 1];

        int answer = 0;

        for(int i = 1; i < firstString.length() + 1; i++){
            for(int j = 1; j < secondString.length() + 1; j++){
                if((firstString.charAt(i - 1) == secondString.charAt(j - 1)) && (LCS[i][j] < j && LCS[i][j] < i)){
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;

                    if(answer < LCS[i][j]){
                        answer = LCS[i][j];
                    }
                } else{
                    if(LCS[i - 1][j] >= LCS[i][j - 1]){
                        LCS[i][j] = LCS[i - 1][j];
                    } else{
                        LCS[i][j] = LCS[i][j - 1];
                    }
                }
            }
        }

        bufferedWriter.write(String.valueOf(answer));
        bufferedWriter.flush();
        bufferedWriter.close();
        bufferedReader.close();
    }
    
}

---

(6) 실행결과

---