boj9251 LCS

링크

9251번: LCS

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

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

출력

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

나의 풀이

• LCS 알고리즘구현.
  1. LCS 2차원 배열을 생성한다.
     • 비교하는 문자열의 길이의 +1 한 값을 가로 세로에 배치한다.
  2. 가로 세로 값을 비교하여 LCS 배열에 채워 넣는다.
     • 값이 같은 경우
       • L[i][j]=L[i-1][j-1]+1
     • 값이 다른 경우
       • L[i][j]=Math.max(L[i-1][j],L[i][j-1])
• 핵심 코드

  int[][] dp = new int[target.length+1][result.length+1];
          int answer = 0;
          for (int i = 0; i < target.length; i++) {
              for (int j = 0; j < result.length; j++) {
                  if(target[i].equals(result[j])){
                      dp[i+1][j+1]=dp[i][j]+1;
                  }else{
                      dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                  }
                  if(answer<dp[i+1][j+1]) answer = dp[i+1][j+1];
              }
          }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  
  public class boj9251 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String[] target = br.readLine().split("");
          String[] result = br.readLine().split("");
          int[][] dp = new int[target.length+1][result.length+1];
          int answer = 0;
          for (int i = 0; i < target.length; i++) {
              for (int j = 0; j < result.length; j++) {
                  if(target[i].equals(result[j])){
                      dp[i+1][j+1]=dp[i][j]+1;
                  }else{
                      dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                  }
                  if(answer<dp[i+1][j+1]) answer = dp[i+1][j+1];
              }
          }
  
          System.out.println(answer);
  
      }
  }

결과