[java]LCS - 백준6251

문제

• LCS(백준6251)

풀이

문제 해석을 하자면,

• Find a Longest Common Subsequence 제일 긴 공통된 부분 문자열을 의미하며,
  A문자열과 B문자열이 주어졌을때 이들의 LCS를 구한다는 의미이다.

풀이

• LCS 정리 를 참고

코드

package ProblemSolution.DP_Detail;

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

/**
 * 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
 * `C[i][j] = max( C[i-1][j], C[i][j-1] )	,if A[i]!=B[j]`
 * `C[i][j] = C[i-1][j-1] + 1	,if A[i]==B[j]`
 * `C[i][j] = 0	,if i==0 || j==0`
 */
public class LCS_BOJ9251 {
    public static int[][] D = new int[1005][1005];

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        String A = stk.nextToken();
        stk = new StringTokenizer(br.readLine());
        String B = stk.nextToken();
        // run
        // i==0 || j==0 은 이미 전역으로 인해 0 이므로 생략
        for(int i = 1; i<=A.length();i++) { // D엔 1 index부터, 실제 문자열은 0 index부터
            for(int j = 1; j<=B.length(); j++) {
                if(A.charAt(i-1)==B.charAt(j-1)) D[i][j] = D[i-1][j-1]+1;
                else D[i][j] = Math.max(D[i-1][j], D[i][j-1]);
            }
        }
        // output
        System.out.println(D[A.length()][B.length()]);

    }
}

느낀점

생략