[Java] 백준 9251 : LCS

문제 링크

1.

LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제

 

2차원 DP 배열을 구성하면 될 것이라 생각했는데, 비효율적으로 구성하다 보니 코드 짜기가 막막했다.

 

좀 더 획기적인 방법이 필요했다.

어렵다. 지친다.

 

 

2.

dp 배열의 행은 비교당할 문자열 (CAPCAK ), 열은 비교할 문자열 (ACAYKP ) 이다.

 

dp[i][j] 는 문자열 b의 i번째, 문자열 a의 j번째 위치까지 구해진 LCS의 값이다.

 

ACAYKP

CAPCAK

dp[3][2] = 1

 

ACAYKP

CAPCAK

dp[3][3] = 2

 

ACAYKP

CAPCAK

dp[3][6] = 3

 

 

j번째 알파벳이 i번째 알파벳과 같으면 1이 증가한다. 어떤 값에서 1이 증가할까?

고민해보면, 그 전까지의 공통부분 수열에서 공통 부분 문자 하나가 하나 더 생기는 것이므로

 

j번째 알파벳과 i번째 알파벳이 같을 때, dp[i][j] = dp[i-1][j-1] + 1 라는 점화식을 구할 수 있다.

 

다를 땐 어떻게 될까?

 

ACAYKP

CAPCAK

dp[4][3] = 2

 

ACAYKP

CAPCAK

dp[4][4] = 2

 

j번째 알파벳과 i번째 알파벳이 다를 땐, 그 전까지의 공통부분 수열의 값과 동일하다.

그러므로, dp[i][j] = dp[i][j-1]의 값과 동일하다.

 

한편, 

ACAYKP

CAPCAK

dp[2][3] = 2

 

ACAYKP

CAPCAK

dp[3][3] = 2

 

이러한 경우도 있으므로 dp[i][j] = dp[i-1][j]의 식도 나올 수 있다.

 

결국엔 두 LCS 중 최댓값을 선택한다.

 

 

정리하면, a 문자열과 b 문자열의 각 알파벳을 일일이 비교하는데

알파벳이 같다면 dp[i][j] = dp[i-1][j-1] + 1

알파벳이 다르면 dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) 이다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        char[] a = sc.next().toCharArray();
        char[] b = sc.next().toCharArray();

        int[][] dp = new int[b.length + 1][a.length + 1];

        for (int i = 1; i <= b.length; i++) {
            for (int j = 1; j <= a.length; j++) {
                if (b[i - 1] == a[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[b.length][a.length]);
        sc.close();
    }
}

 

 

4.

오늘 어려운 문제만 2개 풀었더니 멘탈이 흔들린다.

 

학(學) 했으니, 습(習)하자.

 

 

[참고] https://jaesungbong.tistory.com/21

[참고] https://lotuslee.tistory.com/4