[JAVA] 백준 q9251 - LCS

9251번: LCS

의식의 흐름

이차원 배열 만들어서 하나씩 비교하면서 가능한 수를 저장하면 될 것 같은데...?
(글자 수 = 최대 1000개 => 1000*1000 => 시간 가능)

 

풀이 과정

1. 첫째불과 둘째줄에 입력 받은 문자열을 각각 배열(input1, input2)에 저장한다.
-> 지금 생각해보니 문자열을 굳이 배열에 저장안하고 나중에 .charAt() 써도 됐을듯하다.

2. input1[j]와 input2[i]를 비교하여 배열(dp)에 가능한 부분 수열의 최대 길이를 담는다.

• 두 값이 같은 경우, dp[j+1][i+1] = dp[j][i]+1;
• 두 값이 다른 경우, dp[j+1][i+1] =  Math.max(dp[j+1][i], dp[j][i+1]);

3. input1, input2의 모든 문자에 대해 2번 과정을 반복한다.

4. 2번-3번 과정에서 나온 dp[][]의 값 중 최대값(max)이 가능한 부분 수열의 최대 길이이므로 이를 출력한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[][] dp;
    public static int max = 0;
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input1 = br.readLine().split("");
        String[] input2 = br.readLine().split("");

        dp = new int[input2.length+1][input1.length+1];
        for(int i=0;i<input1.length;i++){
            for(int j=0;j<input2.length;j++){
                if(input1[i].equals(input2[j])){
                    dp[j+1][i+1] = dp[j][i]+1;
                    max = Math.max(dp[j+1][i+1], max);
                }
                else{
                    dp[j+1][i+1] =  Math.max(dp[j+1][i], dp[j][i+1]);
                }
            }
        }

        bw.write(Integer.toString(max));
        bw.flush();
        
        br.close();
        bw.close();
    }
}