[DP][Java][BOJ] #9251. LCS

#DP  #Gold5

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

🌷 문제 설명

✏️ 백준 연습문제: #2470. LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

⌨️ 입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

🖨️ 출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

입출력 예

입력	출력
5 -2 4 -99 -1 98	4

 

💡 해결 포인트

해결...ㅠ못함

 

겸둥이 블로그에서 가져왔다. 지금 졸려서 뭐 안보이기 때문에... 내일 출근길에 읽어볼게..

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

🌷 내 코드

1.

import java.io.*;
import java.util.*;

public class BOJ_9251 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] arr = br.readLine().split("");
    String[] arr2 = br.readLine().split("");

    int[][] dp = new int[arr.length + 1][arr2.length + 1]; //

    for (int i = 1; i <= arr.length; i++) {
      for (int j = 1; j <= arr2.length; j++) {
        if (arr[i - 1].equals(arr2[j - 1])) { // 같은 문자열이면
          dp[i][j] = dp[i - 1][j - 1] + 1; // 대각선 위의 값 + 1
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 왼쪽과 위쪽 중 큰 값
        }
      }
    }

    System.out.println(dp[arr.length][arr2.length]);
  }  
}

 

🌷 코멘트

아 오랜만에 느껴보는 싸피 1학기 느낌.... 아무것도 모르는 나
다시 똑같은거 풀라고 해도 틀릴 확률 100%

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com