[Baekjoon] 백준 9251번: LCS (JAVA)

문제 9251

9251번: LCS

[ 문제 풀이 ]

LCS는 DP를 활용하여 풀 수 있습니다. DP의 가장 큰 특징은 DP 배열의 값들이 모두 답이어야 한다는 것입니다. 즉, 미리 구해둔 답을 이용해서 다음에 올 답을 계산하는 것입니다.

이 문제에서 각 문자열의 길이를 구하여 dp[][] 이차원 배열을 만들면, 아래 그림과 같습니다.

dp[][]

위의 2차원 배열을 순회하면서 각 위치에서 문자를 비교하여 최대로 겹치는 순열을 찾아 개수를 넣어주면 됩니다. 이 때, 두 가지의 경우로 나누어서 계산해주어야 합니다.

1) 해당 위치에서 문자가 일치하는 경우
현재 위치의 값은 이전(i-1, j-1) 값에서 1을 더해줍니다.

2) 해당 위치에서 문자가 일치하지 않는 경우
현재 위치까지 일치한 문자들이 최대한 많은 것으로 계산해주어야 하므로, 왼쪽 값과 위쪽 값 중 큰 값을 저장합니다.

답은 맨 마지막 위치인 dp[str2의 길이][str1의 길이]가 됩니다.

[ 코드 ]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str1 = br.readLine();
        String str2 = br.readLine();

        int size1 = str1.length();
        int size2 = str2.length();

        char[] char1 = new char[size1+1];
        char[] char2 = new char[size2+1];
        for (int i = 1; i < size1+1; i++) char1[i] = str1.charAt(i-1);
        for (int i = 1; i < size2+1; i++) char2[i] = str2.charAt(i-1);

        int[][] dp = new int[size2+1][size1+1];
        for (int i = 1; i < size2+1; i++) {
            for (int j = 1; j < size1+1; j++) {
                // 해당 위치에서 문자 일치
                if (char2[i] == char1[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else { // 일치 X
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // 최대한 일치한 개수로 계산
                }
            }
        }

        bw.write(String.valueOf(dp[size2][size1]));
        bw.flush();
    }
}