[백준9251] LCS / Java

문제주소 :www.acmicpc.net/problem/9251

9251번: LCS

---

<문제 설명>

문제

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

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

입력

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

출력

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

예제 입력

ACAYKP
CAPCAK

예제 출력 

4

 

<풀이법>

▒ 한줄 개념: 동적계획법 ▒ 

동적 계획법 알고리즘 중 하나인 LCS 알고리즘을 사용해서 푸는 문제입니다.

LCS 알고리즘에서 두 가지 문자열에 대해 dp를 만들면 다음과 같습니다.

그림과 같은 방식으로 비교해나가며 dp를 채우게 되는데, 총 2가지 경우로 나누어 점화식을 작성하게 됩니다.

 

▶case 1: str1과 str2의 문자가 같을 경우 - 대각선 위 +1

 

▶case 2: str1과 str2의 문자가 다를 경우 - max(위, 왼쪽)

 

이 두 가지 점화식을 코드로 구현하면 dp가 간단하게 만들어집니다.

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class _9251_LCS {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        int[][] dp = new int[A.length()+1][B.length()+1];
        for(int i = 1; i < A.length()+1; i++){
            for(int j = 1; j < B.length()+1; j++){
                if(A.charAt(i-1) == B.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        System.out.println(dp[A.length()][B.length()]);
    }

    static int max(int a, int b){
        return a > b ? a : b;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest