[Java] 백준 LCS

1. 문제 분석

LCS, 즉 각 문자의 수열에서 공통된 부분을 가진 수열의 최대 길이를 구하는 문제다.

처음에는 모든 문자열의 수열을 구해 문제를 해결할려고 했지만 도저히 구하지 못해 DP로 문제를 해결했다.

 

먼저 DP 테이블을 만들어보자. 행은 1번째 문자열, 열은 2번째 문자열을 넣어주었다.

	A	C	A	Y	K	P
C
A
P
C
A
K

다음과 같은 형태가 나오고 열을 기준으로 하나씩 구해보자.

1.  A일 때

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

({A},{C}), ({A}, {CA}), ({A}, {CAP}), ..., ({A}, {CPACAK})까지 구한 값이다.

A랑 곂친다면 공통된 부분은 {A}가 되기때문에 1을 더해줬다.

2. AC일 때

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

다음은 {AC}를 기준으로 보자.

({AC}.{C}), ..., ({AC}, {CAPC}), ({AC},{CAPCAK})까지 구한 값이다.

마찬가지로 공통된 부분이 있다면 1을 더해줬다.

 

중간에 ({AC}, {CAPC})를 보자. AC에서 추가적으로 C가 만나 {AC}라는 수열을 얻을 수 있었다.

3. ACA일 때

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

다음은 {ACA}를 기준으로 본다.

맨 처음 {ACA}, {C}를 비교할 때 이미 {C}가 곂치는 상황이다. 행을 기준으로 데이터를 가져온 것이다.

 

{ACA},{CA}를 보면 {CA}라는 수열이 만들어진다. 그러므로 1을 더해줘야한다.

 

이제 {ACA},{CAPCA}의 경우 {ACA}가 만들어진다.

앞선 결과에서 이미 {ACA},{CAPC} -> {AC}라는 수열이 만들어진 상태다. 그러므로 1을 추가해주면 된다.

4. ACAY일 때

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

마찬가지로 {ACAY},{C}를 비교했을 때 이미 {C}라는 수열을 가지게 된다. 행을 기준으로 데이터를 가져온 것이다.

두번째로 {ACAY},{CA}를 비교했을 때도 이미 {CA}라는 수열을 가진다.

마지막도 보면 {ACAY},{CAPCAK}는 {ACA}라는 수열을 가진다.

5. ACAYKP일 때

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

위와 동일하므로 마지막만 보자. {ACAYK},{CAPCAK}는 {ACAK}라는 수열을 가진다.

그렇다면 값이 증가할 때 열의 기준으로만 증가할까? 아니다. 문자가 추가되기 전을 기준으로 본다.

{ACAYK},{CAPCAK}에서 K가 추가됨으로 1을 추가해준 것이다.

그래서 우리는 이전단계(대각선)을 기준으로 1을 추가해준다.

6. ACAYKP일 때

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

마찬가지로 값을 더해주면 된다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

        int[][] dp = new int[firstInput.length + 1][secondInput.length + 1];
        for (int i = 1; i <= firstInput.length; i++) {
            for (int j = 1; j <= secondInput.length; j++) {
                //같은 문자 -> 두 글자가 추가되기 전 가장 큰 길이 + 1
                if(firstInput[i-1] == secondInput[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[firstInput.length][secondInput.length]);
    }
}

위의 예시에서는 열이 더 높은 경우가 없었지만 우리의 기준은 문자를 추가하기 전이다.

그러므로 dp[i-1][j], dp[i][j-1]중 큰 값을 구해야한다.

3. 마무리

봐도 봐도 이해가 안간다.. 블로그에도 내가 모르는 부분을 정확히 알려주는 곳이 없어 한참을 해맸다.