[Java] 9251번: LCS Gold 5

문제 링크

DP 방식으로 생각해보자~

DP 문제를 풀 때는,

1. DP 배열을 정의한다.
2. DP[i]가 어떻게 만들어지는지 고민한다.

이렇게 풀어야 한다!

1. DP 배열 정의

두 수열이 있으니, 당연히 두 수열을 모두 살펴봐야한다.
각 수열의 각 문자 하나씩 생각해주어야 하는데, 그렇다면 당연히 2차원 배열로 정의해야 한다.
그래서 DP[i][j]의 형태가 된다.

각 수열을 A와 B라고 했을 때, DP[i][j]는 수열 A를 i까지 살펴봤을 때, 수열 B를 j까지 살펴봤을 때의 최장 길이라고 할 수 있다!

2. DP[i][j]가 어떻게 만들어질까?

하나씩 생각해보다 보면 규칙을 찾을 수 있을 것이다!

각 수열의 문자를 모두 확인해봐야하니 2중 for문으로 풀어야 한다.

그럼 첫 번째 수열의 첫 번째 문자 A와 두 번째 수열을 비교해보자.

↓
ACAYKP
CAPCAK

1. DP[1][1]: A != C, 따라서 0이다.
2. DP[1][2]: A == A, 따라서 1이다.
3. DP[1][3]: A != P, 그러나 1이다.
   • 왜 1일까? 당연히 이전까지의 최댓값을 가져오면 되기 때문이다.
4. DP[1][4]: A != C, 위와 같은 이유로 1이다.
5. DP[1][5]: A == A,
   • 같은 문자를 발견했지만, 그렇다고 해서 길이가 늘어나지는 않는다. 따라서 1이다.
6. DP[1][6]: A != K, 따라서 1이다.

DP 배열은 이렇게 됐을 것이다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
Y	0	0	0	0	0	0	0
K	0	0	0	0	0	0	0
P	0	0	0	0	0	0	0

여기까지는 별다른 규칙이 없다.

첫 번째 수열의 두 번째 문자 C와 두 번째 수열을 비교해보자

 ↓
ACAYKP
CAPCAK

1. DP[2][1]: C == C, 따라서 1이다.
2. DP[2][2]: C != A, 따라서 1이다.
3. DP[2][3]: C != P, 따라서 1이다.
4. DP[2][4]: C == C,
   • 같은 문자를 발견했다. 이전과 같이 1일까? 이때는 길이가 2로 증가한다.
     어떻게 그럴 수 있을까?
     눈으로 직접 수열을 살펴본다면 첫 번째 수열에서는 AC를,
     두 번째 수열에서도 AC를 찾을 수 있으니 2가 되는 것이 당연하다.
     근데 이걸 DP 배열에서는 어떻게 결정할 수 있는 걸까?
     2가 될 수 있었던 이유는, 그 전에 1이 있었다는 것인데 그 1은 어떤 값을 가져온 걸까?
     그 1은 바로 DP[1][3]에서 가져온 것이다.
     즉, 첫 번째 수열의 1번 째 문자와 두 번째 수열의 3번째 문자까지 살펴봤을 때, 둘은 이미 같은 문자열 한 개를 공유하고 있기에 최장 길이가 1이었던 상태다.
     그리고 DP[2][4]까지 살펴본 결과, 두 수열 사이에 같은 문자를 하나 더 발견했기에 최장 길이가 2가 될 수 있었던 것이다.
     이것을 점화식으로 표현하면 DP[i][j] = DP[i-1][j-1] + 1이 된다!
5. DP[2][5]: C != A, 따라서 이전의 최장 길이 2이다.
6. DP[2][6]: C != K, 따라서 이전의 최장 길이 2이다.

이까지 살펴보면 규칙을 다 찾은 것이다!

2중 for 문을 통해서 두 수열을 모두 비교하고,

1. 비교하는 문자가 같으면, DP[i][j] = DP[i-1][j-1] + 1
2. 비교하는 문자가 다르면, DP[i][j] = max(DP[i][j-1], DP[i-1][j]
   • 위에 설명에서는 DP[i][j-1]만 고려했는데, DP[i-1][j]도 고려해야 한다.
     첫 번째 수열에서는 A, 두 번째 수열에서는 C를 살펴보고 있는 상황을 생각해보자.
     DP[i][j-1]은 DP[3][0]이 되어서 0이기에 DP[i][j]는 0이 되어야 한다.
     그러나 실제로는 C가 공통으로 존재하기에 1이다.
     그렇다면 이 값은 어디에 저장돼 있을까?
     배열상 바로 위에서 가져오는 것이다.
     바로 위면 DP[i-1][j]를 말하는 것인데, 이때 실제 값은 DP[2][1]이다.
     이것은 첫 번째 문자의 C와 두번째 수열의 C를 비교한 값이고, 1이다.
     그리고 이전의 최대 길이가 당연히 현재값을 갱신할 때 사용되어야 하므로,
     이 때 DP[i-1][j]를 사용해야 하는 것이다!

  ↓
ACAYKP
CAPCAK
↑

DP 배열을 마저 완성하면 이렇게 된다.

정답

import java.io.*;

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

        // 수열 입력 받기
        char[] seriesA = br.readLine().toCharArray();
        char[] seriesB = br.readLine().toCharArray();

        // DP
        int lA = seriesA.length;
        int lB = seriesB.length;
        int[][] dp = new int[lA + 1][lB + 1]; // 길이만 구하면 되기에 값만 저장하면 된다
        for (int i = 1; i <= lA; i++) {
            for (int j = 1; j <= lB; j++) {
                // 두 수열의 직전 인덱스까지의 최대 길이 + 1
                if (seriesA[i - 1] == seriesB[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[lA][lB]);
    }
}