[백준/15482] 한글 LCS - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 한글 LCS

🦧 문제 풀이 접근

LCS문제의 한글 버전이다.
2차원 배열 DP를 선언한다.
각각의 문자열을 한글자씩 비교한다.

같은 글자일 경우 DP[i-1][j-1]에 +1한다.
다른 글자일 경우 DP[i-1][j]와 DP[i][j-1]의 최대값으로 설정한다.

💻 code

import java.util.*;
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()+1;i++) {
            for(int j=1;j<str2.length()+1;j++) {
                if(str1.charAt(i-1)==str2.charAt(j-1))
                    DP[i][j] = DP[i-1][j-1]+1;
                else
                    DP[i][j] = Integer.max(DP[i-1][j],DP[i][j-1]);
            }
        }
        System.out.println(DP[str1.length()][str2.length()]);
    }
}

🥇 결과

🎓 느낀점

LCS알고리즘을 이용한 문제다. 간단한 알고리즘인 만큼 잘 익혀야한다.