[BOJ/DP+Back-Tracking] 백준 9251 - LCS / 9252 - LCS 2 (Java)

9251 - LCS

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

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)
: 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기
ex. ACAYKP, CAPCAK의 LCS: ACAK

입력: 첫째 줄과 둘째 줄에 알파벳 대문자로 이뤄진 두 문자열 주어짐 (최대 1000글자)
출력: 주어진 두 문자열의 LCS 길이

---

풀이

• `dp[i][j]`: str1의 i번째 문자까지, str2의 j번 문자까지 고려했을 때 LCS 길이
  • `str1[i - 1] == str2[j - 1]` -> `dp[i][j] = dp[i - 1][j - 1] + 1`
    => 두 문자 같으면 지금 문자를 LCS에 포함
  • `str1[i - 1] != str2[j - 1]` -> `dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])`
    => 두 문자 다르면 한쪽 문자 무시하고 최대값 유지

int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (str1.charAt(i - 1) == str2.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]);
    }
}

---

예시

세로 i = str1의 i번째 문자 / 가로 j = str2의 j번째 문자

=> `dp[i][j]` = str1[0...i], str2[0...j]까지 봤을 때 LCS 길이

 

ACAYKP / CAPCAK

• i = 1, j = 2
  • str1[0] = 'A' / str2[1] = 'A' -> str1 == str2
    => dp[1][2] = dp[0][1] + 1 = 0 + 1 = 1
  • 공통 부분 수열: A
• i = 2, j = 1
  • str1[1] = 'C' / str2[0] = 'C' -> str1 == str2
    => dp[2][1] = dp[1][0] + 1 = 1
  • 공통 부분 수열: C
• i = 3, j = 2
  • str1[2] = 'A', str2[1] = 'A' -> str1 == str2
    => dp[3][2] = dp[2][1] + 1 = 2
  • 공통 부분 수열: CA

=> str1과 str2 모든 문자 쌍 비교하면서 같을 때는 대각선 + 1, 다를 때는 위/왼쪽 중 큰 값으로 채워 LSC 길이 완성

---

코드

import java.io.*;

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

        String str1 = br.readLine();
        String str2 = br.readLine();

        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.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]);
            }
        }

        System.out.println(dp[n][m]);
    }
}

---

9252 - LCS 2

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

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)
: 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기
ex. ACAYKP, CAPCAK의 LCS: ACAK

입력: 첫째 줄과 둘째 줄에 알파벳 대문자로 이뤄진 두 문자열 주어짐 (최대 1000글자)
출력
첫째 줄: 주어진 두 문자열의 LCS 길이 (0인 경우 둘째 줄 X)
둘째 줄: LCS (여러 가지인 경우 아무거나 출력)

---

풀이

• `dp[i][j]`: str1의 i번째 문자까지, str2의 j번 문자까지 고려했을 때 LCS 길이
  • `str1[i - 1] == str2[j - 1]` -> `dp[i][j] = dp[i - 1][j - 1] + 1`
    => 두 문자 같으면 지금 문자를 LCS에 포함
  • `str1[i - 1] != str2[j - 1]` -> `dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])`
    => 두 문자 다르면 한쪽 문자 무시하고 최대값 유지

int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (str1.charAt(i - 1) == str2.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]);
    }
}

 

실제 수열: 역추적(Backtracking)

`dp[len1][len2]`부터 `i`, `j` 거꾸로 내려가며 어떤 문자 선택했는지 추적

int i = n, j = m;
while (i > 0 && j > 0) {
    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
        sb.append(str1.charAt(i - 1));
        i--;
        j--;
    }
    else if (dp[i - 1][j] > dp[i][j - 1]) i--;
    else j--;
}

sb.reverse();

---

코드

import java.io.*;

// LCS 2
public class boj_9252 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String str1 = br.readLine();
        String str2 = br.readLine();

        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.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]);
            }
        }

        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                sb.append(str1.charAt(i - 1));
                i--;
                j--;
            }
            else if (dp[i - 1][j] > dp[i][j - 1]) i--;
            else j--;
        }

        sb.reverse();

        System.out.println(dp[n][m]);
        if (dp[n][m] > 0) System.out.println(sb);
    }
}