[JAVA]백준 9251번: LCS

www.acmicpc.net/problem/9251

9251번: LCS

 

1. 문제 설명

 

두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 길이를 찾는 문제이다.

 

재귀 함수로 dp로 구현한 문제.

 

cache 배열 값의 의미는 문자열을 cache 배열의 인덱스부터 끝까지 잘랐다고 하였을 때 그 문자열들의 LCS 값이다.

 

dp 함수의 인수로 첫 번째 문자열 인덱스와 두 번째 문자열 인덱스를 준다.

 

만약 이미 이 위치의 LCS 값을 계산한 적이 있다면 저장된 cache 값을 반환하고

 

계산하지 않았다면 계산한다.

 

여기서 두 가지 경우의 수가 생기는데 인수로 주어진 첫 번째 문자열 인덱스와 두 번째 문자열 인덱스의 문자 값이 같을 경우와 다를 경우이다.

 

같은 경우에는 현재 위치도 LCS 값으로 포함하기 위해 길이를 1 더하고, 첫번째, 두 번째 문자열 인덱스 모두 증가시키면 된다.

 

다를 경우에는 다시 두 가지 경우가 생기게 된다.

 

첫번째 인덱스만 증가시킬지, 두 번째 인덱스만 증가시킬지이다.

 

두 가지 모두 dp로 재귀호출하여 값을 저장하고

 

모든 경우에서의 최대값을 cache에 저장하고 return 한다.

 

 

 

 

2. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int[][] cache=new int[1001][1001];
    public static String input_str_1="";
    public static String input_str_2="";

    public static int input_str_1_size=0;
    public static int input_str_2_size=0;

    public static void main(String[] args) throws IOException {
        Scanner scan=new Scanner(System.in);

        input_str_1=scan.next();
        input_str_2=scan.next();

        input_str_1_size=input_str_1.length();
        input_str_2_size=input_str_2.length();

//        long start=System.currentTimeMillis();

        // 배열 값 초기화
        for(int x=0;x<=1000;x++){
            for(int y=0;y<=1000;y++)
                cache[x][y]=-1;
        }

        System.out.println(dp(0,0));

//        long end=System.currentTimeMillis();
//
//        System.out.println(end-start);

        scan.close();


    }

    public static int dp(int one,int two){

        if(one>=input_str_1_size || two>=input_str_2_size)
            return 0;


        if(cache[one][two]!=-1)
            return cache[one][two];

        char base=input_str_1.charAt(one);

        int max_value=0;

        int temp_value=0;

        if(base==input_str_2.charAt(two))
            temp_value = dp(one + 1, two + 1) + 1;
        else
            temp_value = Math.max(dp(one + 1, two),dp(one,two+1));

        if (max_value < temp_value)
            max_value = temp_value;

        cache[one][two]=max_value;

        return max_value;
    }



}