[백준 BOJ 9251번] LCS

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

9251번: LCS

 

1. 문제

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

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

---

2. 입력

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

 

ACAYKP
CAPCAK

---

3. 출력

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

 

 

4

---

4. 풀이

이 문제는 사실상 암기를 하는 것이 편하지 않을까? 일단 두 배열에 대해서 입력을 받은 후 비교 시 같다면, (x-1,y-1)+1을, 다르다면 (x-1,y)와 (x, y-1) 중 큰 값을 넣어준다. 이 과정을 수행 시 NullPointer가 뜨지 않도록 조심해주어야 한다. 또한, Top-Down방식에서 main함수에서 for문을 사용해서 Lcs(i)함수를 i=0부터 끝까지 돌려주지 않아도 되는데 이는 Lcs함수에서 단순히 if문 내에만 Lcs재귀함수가 있는게 아니라 else문에서도 Lcs재귀함수가 두개나 출현하기에 굳이 for문을 돌리지 않아도 된다.

 

---

5. 소스코드

<Top-Down 방식>

 

import java.io.*;
 
public class Main {
    static Integer [][] dp;
    static String [] arr1;
    static String [] arr2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();

        arr1 = str1.split("");
        arr2 = str2.split("");

        dp = new Integer [str1.length()][str2.length()];

        Lcs(str1.length()-1, str2.length()-1);

        System.out.println(dp[str1.length()-1][str2.length()-1]);

    }

    public static int Lcs(int a, int b){
        if(a == -1 || b == -1) return 0;
        else{
            if(dp[a][b] == null){
                dp[a][b] = 0;
                if(arr1[a].equals(arr2[b])) dp[a][b] = (int)Lcs(a-1, b-1)+1;

                else{ dp[a][b] = (int)Math.max(Lcs(a-1, b), Lcs(a, b-1)); }
            }
        }
        return dp[a][b];
    }
}

<Bottom-Up 방식>

 

import java.io.*;
 
public class Main {
    static int [][] dp;
    static String [] arr1;
    static String [] arr2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();

        arr1 = str1.split("");
        arr2 = str2.split("");

        dp = new int [str1.length()+1][str2.length()+1];

        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); j++){
                if(arr1[i-1].equals(arr2[j-1])) dp[i][j] = dp[i-1][j-1] + 1;
                else{ dp[i][j] = (int)Math.max(dp[i-1][j], dp[i][j-1]); }
            }
        }
        System.out.println(dp[str1.length()][str2.length()]);

    }
}

---

6. 배운 것

char형 비교는 A==B, String형 비교는 Arr1.equals(Arr2)이다.