[백준] 9251번 LCS _ JAVA ( 주석 설명 )

풀이

1) dp 정의

- 입력받은 첫번째 문자열을 char_one[], 두번째 문자열을 char_two[] 라고 할 때

각각 i, j번째까지의 부분 수열 중, 공통되는 부분 수열을 찾아 그 중 제일 긴 것을 dp[i][j]에 저장한다.



2) 점화식

if(char_one[i] == char_two[j])

	dp[i][j] = dp[i-1][j-1] + 1;

else

	dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

 

https://st-lab.tistory.com/139

[백준] 9251번 : LCS - JAVA [자바]

 

---

 

1번

→ Top-down 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Integer[][] dp; //공통되는 부분 수열이 길이가 최대 몇까지 되는지 담는 공간
    static char[] char_one; //입력받은 첫번째 문자열을 char[] 배열로 변환, 문자 비교를 위해
    static char[] char_two; //입력받은 두번째 문자열를 char[] 배열로 변환, 문자 비교를 위해

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char_one = br.readLine().toCharArray();
        char_two = br.readLine().toCharArray();

        dp = new Integer[char_one.length][char_two.length];

        //맨 꼭짓점에서는 제일 긴 공통되는 부분 수열(LCS)가 저장된다.
        System.out.println(LCS(char_one.length-1, char_two.length-1));
    }

    //Top-down 방식
    private static int LCS(int one, int two) {
        //범위 out
        if(one==-1 || two==-1)
            return 0;

        if(dp[one][two] == null) {
            dp[one][two] = 0;
            //큰 문제를 작은 문제로 계속 쪼갠다.
            //표로 그려봤을 때, 이와 같은 규칙을 찾을 수 있다.
            if (char_one[one] == char_two[two]) {
                dp[one][two] = LCS(one-1, two-1) + 1;
            } else
                dp[one][two] = Math.max(LCS(one-1, two), LCS(one, two-1));
        }

        return dp[one][two];
    }
}

 

---

 

2번

→ Bottom-up 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] dp; //공통되는 부분 수열이 길이가 최대 몇까지 되는지 담는 공간
    static String one; //입력받은 첫번째 문자열
    static String two; //입력받은 두번째 문자열
    static char[] char_one; //one을 char[] 배열로 변환, 문자 비교를 위해
    static char[] char_two; //two를 char[] 배열로 변환, 문자 비교를 위해

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        one = br.readLine();
        two = br.readLine();

        char_one = one.toCharArray();
        char_two = two.toCharArray();

        //+1을 함으로써 dp[0][0], dp[i-1][j-1] 공간 탐색할 때 범위 체크를 피해준다. 
        dp = new int[one.length()+1][two.length()+1];

        LCS2(one.length(), two.length());

        //맨 꼭짓점에서는 제일 긴 공통되는 부분 수열(LCS)가 저장된다. 
        System.out.println(dp[one.length()][two.length()]);
    }
    
    //Bottom-up 방식
    private static void LCS2(int one, int two) {
        for(int i=0;i<one;++i){
            for(int j=0;j<two;++j){
                //표로 그려봤을 때, 이와 같은 규칙을 찾을 수 있다.
                if(char_one[i] == char_two[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]);
            }
        }
    }
}