[백준] 9251번 - LCS [Java]

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

 

[백준] 9251번 - LCS [Java]

[백준] 9251번 - LCS [Java]

---

1.  아이디어

 

문제 이름처럼 다이다믹 프로그래밍을 활용한 LCS 알고리즘으로 해결할 수 있다.

---

2. 문제풀이

 

두 문자열의 길이만큼 행과 열을 갖는 2차원 dp 배열을 만들어준다.

2차원 배열의 두 인덱스는 각 문자열의 문자와 매핑시킬 수 있는데 두 문자가 서로 같을 경우 두 문자가 없었던 dp[i-1][j-1]일 때 LCS의 길이에서 +1 이 되고 두 문자가 서로 다르면 dp[i-1][j]와 dp[i][j-1] 중 큰 LCS를 갖는다.

---

3. 코드

 

import java.io.*;

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();

        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[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[N][M]);
    }
}

---

4. 후기