[백준] 15482번 - 한글 LCS [Java]

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

 

[백준] 15482번 - 한글 LCS [Java]

[백준] 15482번 - 한글 LCS [Java]

---

1.  아이디어

 

이전 LCS 문제에서 문자열이 한글로 주어진 문제로 자바에서는 char 타입으로 한글 문자도 다룰 수 있어서 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])

---

2. 문제풀이

 

다이나믹 프로그래밍을 활용한 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. 후기