백준 9252번 LCS2 (JAVA)

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다.

2차원 DP[y][x]를 통해 a의 y번째 글자와 b의 x번째 글자를 비교해 같다면 

DP[y][x] = (DP[y-1][x] , DP[y][x-1] , DP[y-1][x-1] + 1) 중 최대값,

둘의 글자가 다르다면 

DP[y][x] = (DP[y-1][x] , DP[y][x-1] , DP[y-1][x-1] ) 중 최대값으로 초기화하였습니다.

최종 글자는 역순으로 둘의 글자가 같다면 대각선으로 다르다면 위쪽이나 아래쪽으로 이동해 같은 글자라면 결과에 문자를 추가하는 방법으로 해결하였습니다.

 

package BOJ.DP;

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

public class BOJ_9252 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();
        int[][] dp = new int[a.length()][b.length()];
        for(int i = 0 ; i < a.length() ; i++){
            for(int j = 0 ; j < b.length() ; j++){
                int isSame = 0;
                if(a.charAt(i) == b.charAt(j)){
                    isSame = 1;
                }
                int result = isSame;
                if(i != 0){
                    result = Math.max(result, dp[i-1][j]);
                }
                if(j != 0){
                    result = Math.max(result, dp[i][j-1]);
                }
                if(i != 0 && j != 0 ){
                    result = Math.max(result, dp[i-1][j-1] + isSame);
                }
                dp[i][j] = result;
            }
        }
        System.out.println(dp[a.length()-1][b.length()-1]);
        int y = a.length()-1;
        int x = b.length()-1;
        int prev = 0;
        StringBuilder sb = new StringBuilder();
        while(y >= 0 &&  x >= 0){
            if(a.charAt(y) == b.charAt(x)){
                sb.append(a.charAt(y));
                y--;
                x--;
            }else if(y-1 < 0){
                x--;
            }else if(x-1 < 0){
                y--;
            }else if(dp[y-1][x] > dp[y][x-1]){
                y--;
            }else{
                x--;
            }
        }
        System.out.println(sb.reverse().toString());
    }
}