[백준 | Java] 9251 LCS

내 풀이

LCS 문제는 여러 부분 문제로 나눌 수 있으며, 이러한 부분 문제들이 여러 번 중복되어 나타난다.
따라서 2차원 배열에 부분 문제들의 해결 결과를 저장하고 재사용하기 위해 다이나믹 프로그래밍으로 풀었다.

풀이과정은 다음과 같다.

1. 두 문자열의 길이 + 1 크기의 2차원 배열 dp 선언
2. 두 문자열의 각 문자를 비교하며, 공통 부분 수열의 길이를 2차원 배열에 저장
3. 2차원 배열의 마지막 값이 최장 공통 수열의 길이가 됨

위 예제의 최종 dp배열의 결과는 다음과 같다.

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

### 코드
```java
import java.io.*;

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

        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                // 두 문자가 같을 때
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // dp[i-1][j] => str1의 현재 문자까지와 str2의 이전 문자까지의 LCS 길이
                    // dp[i][j-1] => str1의 이전 문자까지와 str2의 현재 문자까지의 LCS 길이
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[str1.length()][str2.length()]);
    }
}