[PS] BOJ9251 LCS ( DP ) with JAVA

9251번: LCS

 

 

◎ 문제풀이

 

LCS에는 두 가지가 있다.

 

1) Longest Common SubSequence 

2) Longest Common SubString

 

전자는 공통되는 최장 부분 수열을 구하는 것이고

후자도 공통되는 최장 부분 수열을 구하는 것이지만 연속으로 이어져 있는 부분수열을 구하는 알고리즘이다.

 

위 문제는 연속으로 이어지지 않고 공통되는 최장부분수열을 구하는 문제이므로,   Longest Common SubSequence 풀이로 풀어야 한다. 

 

[동적계획법] Longest Common SubSequence

[동적계획법] 두 문자열 비교하기 ( Longest Common SubString )

 

두 가지 알고리즘에 대한 자세한 내용은 위 포스팅을 참고하면 된다. 

 

 

LCS 문제에서 DP 풀이를 하려면 DP 테이블을 2차원 배열로 만들어야 한다. 

 

 

 

 

ACAYKP와 CAPCAK를 비교해보자.

 

파란칸에는 AC와 CAP의 최장공통부분수열 길이가 들어가야 한다. 파란칸에 값이 들어가는 경우는 2가지이다.

 

 

 

1) 파란칸의 두 문자가 서로 같은 경우

 

파란칸은 AC와 CAP의 C와 P이다. C와 P는 서로 다르다. 그러므로 이 경우는 고려하지 않는다. 

 

만약 같다면 어떻게 될까?

 

AC와 CAC라고 가정하면, 이는 [ A - CA ]에서 양쪽에 C가 추가된 것이다. 그러므로 [ A - CA ]의 최장공통부분수열의 길이에서 +1한 값이 [ AC - CAC ]의 최장공통부분수열의 길이이라고 할 수 있다. 위 그림으로 보면 대각선으로 이동한 경우이다. 

 

 

2) 파란칸의 두 문자가 서로 다른 경우

 

파란칸은 AC와 CAP의 C와 P는 서로 다르다. 문자가 서로 다르면 파란칸은 최장공통부분수열의 길이에 어떤 영향도 주지 않는다.  그러므로 기존의 길이를 그대로 유지한다. 그런데 기존의 길이의 경우는 2가지가 있다. 

 

1) [ A - CAP ]에서 첫번째 수열에 C가 추가된 경우 

2) [ AC - CA ]에서 두번째 수열에 P가 추가된 경우

 

위 그림으로 보면 좌측에서 위에서 내려오는 경우와 좌측에서 들어오는 경우이다. 

 

[AC - CAP]가 되려면 [ A - CAP ]에 C가 추가된 경우와 [ AC - CA ]에 P가 추가된 경우, 이렇게 2가지가 있는 것이다. 문제는 최장 길이를 구하는 문제이므로 2가지 경우 중 최댓값을 선택하면 된다. 

 

그럼 이를 코드로 확인해보자.

 

 

◎코드

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

import static java.lang.Math.*;

//BOJ9251 LCS
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int[][] dp = new int[str1.length+1][str2.length+1]; //현재에서 대각선,위측,좌측의 값을 가져와야 하므로, 길이를 1씩늘려 index에러를 방지 

        for(int i=1; i<=str1.length;i++) {
            for (int j = 1; j <=str2.length; j++) {
                if (str1[i-1] == str2[j-1]) { // 경우1) 문자가 서로 같은 경우
                    dp[i][j] = dp[i-1][j-1] + 1; // 대각선 방향에서 길이 가져오기
                }
                else { // 경우2) 문자가 서로 다른 경우
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 좌측과 위측 길이 중 최댓값
                }
            }
        }

        System.out.println(dp[str1.length][str2.length]); // 결과 출력
    }
}