[JAVA] 백준 (골드5) 9251번 LCS

링크

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

---

문제 설명

정답률 41.061%
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

---

입력 예제

ACAYKP
CAPCAK

---

출력 예제

4

---

풀이

LCS는 문제 설명대로 공통의 가장 긴 부분 수열이다. ACAYKP와 CAPCAK에선 ACAK가 공통이다.

LCS는 다이나믹 프로그래밍으로 풀 수 있다. 메모이제이션 배열을 2차원으로 생성하여 dp[i][j]는 str1의 i번째 문자까지와 str2의 j번째 문자까지의 LCS의 길이를 저장한다.

메모제이션 배열은 다음과 같이 채울 수 있다.

    C A P C A K
  0 0 0 0 0 0 0
A 0 0 -> A와 C
C 0 1 -> AC와 C
A 0 1 -> ACA와 C
Y 0 1 -> ACAY와 C
K 0 1 -> ACAYK와 C
P 0 1 -> ACAYKP와 C

    C A P C A K
  0 0 0 0 0 0 0
A 0 0 1 -> A와 CA
C 0 1 1 -> AC와 CA
A 0 1 2 -> ACA와 CA
Y 0 1 2 -> ACAY와 CA
K 0 1 2 -> ACAYK와 CA
P 0 1 2 -> ACAYKP와 CA

    C A P C A K
  0 0 0 0 0 0 0
A 0 0 1 1 -> A와 CAP
C 0 1 1 1 -> AC와 CAP
A 0 1 2 2 -> ACA와 CAP
Y 0 1 2 2 -> ACAY와 CAP
K 0 1 2 2 -> ACAYK와 CAP
P 0 1 2 3 -> ACAYKP와 CAP

...

    C A P C A K
  0 0 0 0 0 0 0
A 0 0 1 1 1 1 1
C 0 1 1 1 2 2 2
A 0 1 2 2 2 3 3
Y 0 1 2 2 2 3 3
K 0 1 2 2 2 3 4
P 0 1 2 3 3 3 4

여기서 규칙성을 보면 str1의 i번째 까지의 부분 수열과 str2의 j번째 까지의 부분 수열의 각각 다음 문자가 같을 때 길이가 증가한다.

if (str1[i + 1] == str2[j + 1]) {
	dp[i + 1][j + 1] = dp[i][j] + 1;
}

이 규칙성을 이용해 재귀 함수를 구현한다.

static int lcs(int i, int j) {
    //공백 문자열이 포함될 경우
    if (i == -1 || j == -1) {
        return 0;
    }
    //방문하지 않은 인덱스일 때
    if (dp[i][j] == null) {
        dp[i][j] = 0;
        //str1의 i번째 문자와 str2의 j번째 문자가 같을 때
        if (str1[i].equals(str2[j])) {
            dp[i][j] = lcs(i - 1, j - 1) + 1;
        }
        //같지 않다면 dp[i - 1][j]와 dp[i][j - 1] 중 큰 값으로 초기화
        else {
            dp[i][j] = Math.max(lcs(i - 1, j), lcs(i, j - 1));
        }
    }
    return dp[i][j];
}

전체 코드

//백준
public class Main {

    static String[] str1;
    static String[] str2;
    static Integer[][] dp;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        str1 = br.readLine().split("");
        str2 = br.readLine().split("");
        dp = new Integer[str1.length + 1][str2.length + 1];

        int result = lcs(str1.length - 1, str2.length - 1);
        System.out.println(result);
    }

    static int lcs(int i, int j) {
        //공백 문자열이 포함될 경우
        if (i == -1 || j == -1) {
            return 0;
        }

        //방문하지 않은 인덱스일 때
        if (dp[i][j] == null) {
            dp[i][j] = 0;

            //str1의 i번째 문자와 str2의 j번째 문자가 같을 때
            if (str1[i].equals(str2[j])) {
                dp[i][j] = lcs(i - 1, j - 1) + 1;
            }
            //같지 않다면 dp[i - 1][j]와 dp[i][j - 1] 중 큰 값으로 초기화
            else {
                dp[i][j] = Math.max(lcs(i - 1, j), lcs(i, j - 1));
            }
        }

        return dp[i][j];
    }
}