[백준] 15482번 : 한글 LCS – JAVA [자바]

 

 

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

15482번: 한글 LCS

 

 

 

 

---

• 문제

 

 

---

 

• 풀이 방법

이 문제는 전형적인 DP의 LCS 문제이다. 조금 더 디테일한 풀이는 밑에 링크를 참고하면 되겠다.

https://propercoding.tistory.com/entry/알고리즘-LCS-최장-공통-부분-수열

[알고리즘] LCS (최장 공통 부분 수열)

 

 

---

 

• 풀이

import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s1 = br.readLine();
    String s2 = br.readLine();
    int n = s1.length();
    int m = s2.length();
    int[][] dp = new int[n+1][m+1];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (s1.charAt(i) == s2.charAt(j)) {
          dp[i+1][j+1] = dp[i][j] + 1;
        } else {
          dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
        }
      }
    }
    System.out.print(dp[n][m]);
  }
}

 

 

---

 

• 후기

되게 전형적인 LCS 문제여서 LCS 이론을 아는 사람은 쉽게 풀 수 있는 문제였다.