자바 - 백준 9252 / LCS 2

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

골드4

구현 방법

• 전형적인 DP 문제이다.
• 최대 1000글자 이므로 O(N^2)의 시간복잡도가 가능하다.

 

최대 문자열 길이 구하는 방법

문자가 같은 경우의 점화식

• 같은 문자인 경우, 각각 단어 인덱스를 1씩 증가하여 다음 문자부터 비교 진행
• dp[i][j] = dp[i - 1][j - 1] + 1;

문자가 다른 경우의 점화식

• 다른 문자인 경우, 두 단어 중 한 인덱스만 증가함
• dp[i][j] = Math.*max*(dp[i - 1][j], dp[i][j - 1]);

 

최대 문자열일때의 단어 구하는 방법

• dp의 가장 오른쪽 아래부터 진행한다.(역추적 진행)
  • 가장 오른쪽 아래의 숫자가 최대 문자열의 길이이기 때문이다.
  • 가장 왼쪽 위부터 진행할 경우, 최대값에 도달하지 못할수도 있다.
• 문자가 같은 경우, 가로와 세로 인덱스 모두 감소한다.
• 문자가 다른 경우, 이전 문자열 길이가 큰쪽의 인덱스만 감소한다.
  • 이때, 문자열 길이가 같은 경우에는 어떤 인덱스를 감소시키던 상관없다. 단, 둘 중 하나의 인덱스만 감소시켜야 한다.
    • "LCS가 여러 가지인 경우에는 아무거나 출력"이라는 조건이 있기 때문

코드

import java.io.*;

/**
* 백준 9252
* LCS 2
* 골드4
* https://www.acmicpc.net/problem/9252
*/
public class Boj9252 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] w1 = br.readLine().toCharArray();
        char[] w2 = br.readLine().toCharArray();

        int len1 = w1.length;
        int len2 = w2.length;

        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(w1[i - 1] == w2[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 i1 = len1;
        int i2 = len2;

        while(i1 > 0 && i2 > 0) {
            if(w1[i1 - 1] == w2[i2 - 1]) {
                sb.append(w1[i1 - 1]);
                i1--;
                i2--;
            } else if (dp[i1 - 1][i2] > dp[i1][i2 - 1]) {
                i1--;
            } else {
                i2--;
            }
        }

        System.out.println(dp[len1][len2]);
        System.out.print(sb.reverse());
    }
}