[java] 9251번 LCS

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

최대 1000글자 이므로 , dp 사용

3. 코드

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

public class Main {

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

        String a = br.readLine();
        String b = br.readLine();
        int aLength = a.length();
        int bLength = b.length();

        int[][] dp = new int[aLength+1][bLength+1];
        dp[0][0] = 0;

        for(int i=1;i<aLength+1;i++){
            for(int j=1;j<bLength+1;j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(a.charAt(i-1) == b.charAt(j-1)){
                    dp[i][j] = Math.max(dp[i-1][j-1]+1, dp[i-1][j]);
                }
            }
        }
        System.out.println(dp[aLength][bLength]);
    }
}

A문자의 첫번째줄부터 B문제 전체와 비교하여, 최대 길이를 얻어냄
백준예시 표로 이해

dp[1][j] 일 때,

dp[2][j]일 때

A 문자열 CA 와, B 문자열 AC 까지만 비교했을 때는 1 이지만,

A 문자열 CA 와, B 문자열 ACA 까지 비교하면 2가 됨.
dp[i-1][j-1] + 1 로, 2가 됨.

이리하여, 아래와 같이 제일 긴 문자열은 ACAK 가 됨 !