[Java] 백준 - 9252번: LCS - 2

9월 11일(월) - 다이나믹 프로그래밍 (9252번)

9252번: LCS 2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

("9251번: LCS" 문제의 풀이 + print_LCS 함수 https://jh4995.tistory.com/409)

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

public class Main {

    static char[] string_1, string_2;
    static int[][] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        string_1 = br.readLine().toCharArray();
        string_2 = br.readLine().toCharArray();
        int len_1 = string_1.length;
        int len_2 = string_2.length;

        dp = new int[len_1 + 1][len_2 + 1];

        for(int i=0; i<len_1; i++)
        {
            dp[i][0] = 0;
        }
        for(int j=0; j<len_2; j++)
        {
            dp[0][j] = 0;
        }

        for(int i=1; i<=len_1; i++)
        {
            for(int j=1; j<=len_2; j++)
            {
                if(string_1[i-1] == string_2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        System.out.println(dp[len_1][len_2]);
        print_LCS(len_1, len_2);
    }

    static void print_LCS(int i, int j){
        
        if(dp[i][j] == 0)
        {
            return;
        }

        if(string_1[i-1] == string_2[j-1])
        {
            print_LCS(i-1, j-1);
            System.out.print(string_1[i-1]);
        }
        else
        {
            if(dp[i-1][j] > dp[i][j-1])
            {
                print_LCS(i-1, j);
            }
            else
            {
                print_LCS(i, j-1);
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ