9251번. LCS

 

아이디어

dp[i][j] 를 

1번째 수열의 i번째 문자까지, 2번째 수열의 j번째 문자까지 고려했을 때 LCS 값이라고 정의한다면 dp[i][j] 는 다음과 같은 점화식을 가진다.

 

1번째 수열의 i 번째 문자와 2 번째 수열의 j 번째 문자가 동일한 경우

 

dp[i][j] = dp[i - 1][j - 1] + 1

 

동일하지 않은 경우에는

 

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

 

 

ACAYKP, CAPCAK 가 주어질 경우

 

dp[3][5] 는 ACA 와 CAPCA 의 LCS 값을 의미하게 되고 [3][5] 에 해당하는 문자가 'A' 로 동일하기 때문에 AC 와 CAPC 의 LCS 값에 1 을 추가한 게 곧 ACA, CAPCA 의 LCS 가 된다.

 

dp[2][5] 는 AC 와 CAPCA 의 LCS 값을 의미하는데 [2][5] 해당하는 문자가 서로 다르기 때문에

(AC, CAPC) 의 LCS 값과 (A, CAPCA) 의 LCS 값 중 더 큰 값을 따르게 된다.

 

 

풀이코드

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[] s1 = br.readLine().toCharArray();
        char[] s2 = br.readLine().toCharArray();

        int R = s1.length;
        int C = s2.length;

        int[][] dp = new int[R + 1][C + 1];
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (s1[i - 1] == s2[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[R][C]);
    }
}