백준 9251[자바] java LCS

문제 링크: https://www.acmicpc.net/problem/9251

9251번: LCS

▶문제

LCS(Longest Common Subsequence, 최장 공통부분 수열 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

---

▶입력

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

---

▶출력

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

---

▶해설

표로 예제를 풀어보겠습니다.

String n = ACAYKP 

String m = CAPCAK

m.charAt()과 n.charAt()이 같다면 증가시킵니다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	2
C	1	2	2	2	2	2
A	1	2	3	3	3	3
K	1	2	3	3	4	4

채울 수 있습니다. 

표를 기준으로 아래와 같이 점화식을 세울 수 있습니다. 

for(int i=1; i<=nSize; i++){
    for(int j=1; j<=mSize; j++){
        if(n.charAt(i-1)==m.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]);
        }
    }

전체 코드

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

public class Main {

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

        String n = br.readLine();
        String m = br.readLine();

        int nSize = n.length();
        int mSize = m.length();

        int [][] dp = new int[nSize+1][mSize+1];

        for(int i=1; i<=nSize; i++){
            for(int j=1; j<=mSize; j++){
                if(n.charAt(i-1)==m.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[nSize][mSize]);
    }
}