[백준] 9252번 LCS 2(java)

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

9252번: LCS 2

 

핵심

이 문제는 LCS와 dp를 이용하여 풀 수 있다.

문자열 2개를 비교해 가며, 아래 테이블을 채워나간다.

만약 첫 줄에서 해당 문자가 다르면 0 같으면 1을 넣어준다.

이후 값은 이전의 값을 이어서 갖게 된다.

 

이후 다시 값을 비교하면 첫 번째에 1이 들어가고 두 번째도 1이 들어갈 것이다.

이후에 A와 A가 다시 겹치게 되는데, 무작정 1을 더하면 A를 두 번 사용하게 된 꼴이다.

하지만 우리는 직관적으로 CA가 가능하고 2라는 것을 알 수 있다.

 

나머지 정보들을 살펴보자

윗 행(i - 1)의 값이 의미하는 정보

해당 위치의 바로 윗 행이 의미하는 정보는 두 번째 문자열의 'C'가 해당 위치에서 첫 번째 문자열의 'A'까지 비교하면서 얻은 최대 LCS의 값을 의미한다.

 왼쪽 열(j - 1)의 값이 의미하는 정보

해당 위치의 바로 왼쪽 열이 의미하는 정보는 첫 번째 문자열의 두 번째 문자인 'C'가 해당 위치에서 두 번째 문자열의 'A'까지 비교하면서 얻은 최대 LCS의 값을 의미한다.

윗 행(i - 1), 왼쪽 열(j - 1)의 값이 의미하는 정보

->해당 위치의 윗 행, 왼쪽 열이 의미하는 정보는 현재 문자에 대하여 각 이전 문자열의 이전 문자가 해당 위치에서 가질 수 있는 최대 LCS의 값을 의미한다.

 

즉 아래와 같은 점화식이 만들어진다. 

 

이를 바탕으로 전체적인 테이블을 완성하면 아래와 같다.

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();
        char[] A = new char[a.length() + 1];
        char[] B = new char[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) A[i] = a.charAt(i - 1);
        for (int i = 1; i <= b.length(); i++) B[i] = b.charAt(i - 1);
        int[][] dp = new int[b.length() + 1][a.length() + 1];

        for (int i = 1; i <= b.length(); i++) {
            for (int j = 1; j <= a.length(); j++) {
                if (B[i] == A[j]) 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[b.length()][a.length()]);
        int i = b.length();
        int j = a.length();
        Stack<Character> stack = new Stack<>();
        while (i>=1 && j>=1){
            if (dp[i][j] == dp[i-1][j])i--;
            else if (dp[i][j] == dp[i][j - 1])j--;
            else {
                stack.push(B[i]);
                i--;
                j--;
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }
}

해설

위에 설명한 대로 코드를 짜면, 최대 값을 구할 수 있게 된다.

이후 문제는 문자열을 구하는 것이다.

이는 dp를 역으로 추적하는 방법을 사용하면 된다.

우측하단부터 위, 왼쪽, 왼쪽위대각선을 비교하여 이동하게 된다.

만약 위쪽이나 왼쪽의 값이 같다면, 문자의 추가가 없던 것이 된다.

만약 둘 다 다르다면, 대각선에서 부터 문자가 증가되었으므로, 그 값의 문자열에 넣어주고 대각선으로 이동하게 된다.

 

 

배운 점

처음 이 문제를 풀 때 LCS개념을 몰랐기에 매우 난해했다.

문제를 풀수록 알고리즘을 알고 모르고의 차이가 큰 것 같다는 느낌이 많이 들었다.

따라서 여러 문제를 풀어보며 경험을 늘리고, 여러 알고리즘을 접하여 풀이법을 익혀야겠다.