boj9251 LCS

15250 단어 백준골드DPDP

링크

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);
    
        }
    }

결과

좋은 웹페이지 즐겨찾기