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

 

#풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
       String word1,word2;
       word1 = br.readLine();
       word2 = br.readLine();
       int[][]dp = new int[word2.length()+1][word1.length()+1];

       for(int i = 1; i<word2.length()+1; i++){
           for(int j = 1; j<word1.length()+1; j++){
               if(word2.charAt(i-1)==word1.charAt(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]);
           }
       }
       StringBuilder sb = new StringBuilder();
       int i = word2.length();
       int j = word1.length();
       while(i>0 && j>0){
           if(word2.charAt(i-1)==word1.charAt(j-1)){
               sb.append(word2.charAt(i-1));
               i--;
               j--;

           }
           else if(dp[i-1][j]>dp[i][j-1])i--;
           else j--;
       }


       System.out.println(dp[word2.length()][word1.length()]);
       System.out.println(sb.reverse());

    }
}

#성능

#정리

LCS알고리즘(dp) 문제이다.

dp[i][j]는 word2의 i번째까지, word1의 j번째까지 비교했을 때의 LCS 길이를 의미한다.

점화식은 아래와 같다.
문자가 같으면: dp[i][j] = dp[i-1][j-1] + 1
다르면: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

LCS문자열 구하기: DP 테이블의 오른쪽 아래(dp[n][m])부터 시작해 두 문자가 같으면 해당 문자를 결과 문자열에 추가하고 대각선(↖)으로 이동, 다르면 더 큰 값이 있는 방향(↑ or ←)으로 이동 거꾸로 구했기 때문에 마지막에 reverse()로 뒤집어 출력한다.