[BOJ] 9251 : LCS (Java)

https://www.acmicpc.net/problem/9251

9251번: LCS

걸린 시간 : 1시간 13분

---

난이도 좀 더 쳐줘요.. LCS를 알면 제일 기초여서 난이도가 낮게 책정된 듯.

처음에 무슨 생각이었는지 N 이 1000인데도 불구하고 시간제한이 걸려있어서 O(N^2) 이 불가능하다고 생각했다. 그러다 O(N^2)이 가능한 것을 알고 표를 무작정 그려봤는데,,, 감은 왔지만 정확한 점화식을 생각해내지 못했다.

결국, 답을 보고 풀고 말았다.

알고리즘

다이나믹 프로그래밍 문제이다.

DP에선 항상 일반항 혹은 점화식을 찾는 게 가장 중요한데, 그걸 찾아내지 못했다. 결국 표를 무작정 그려서 귀납적으로 원리를 파악했다.

다음 게시글에 원리가 잘 나와있다.

https://melonicedlatte.com/algorithm/2018/03/15/181550.html

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

	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

 

이런 표를 그려놓고 귀납적으로 원리를 파악해보자. (하지만 난 원래 다이나믹 프로그래밍은 연역적으로 파악해야한다고 생각한다.)

1. 검은색 배경 숫자(1,3)를 보자. CA 와 ACA 사이에 LCS는 2였다. 이 때 ACA 에 Y 가 붙으면, LCS가 늘어나지 않는다. 왤까?
   • 만약 어떤 문자열 str과 ACA 사이에 LCS가 2라고 해보자. 이 때 ACA 에 Y 가 붙었다. str에 AC 든 CA 든 AA 든 존재할 것이고, 그 후에 Y가 있다면 LCS가 늘어날수도 있지 않나??
   • 하지만, 이러려면 (0,3) 에서 이미 3 이었거나, str의 마지막 문자가 Y 이었어야 한다. 이 두 경우가 각각 2번과 3번이다.
2. 빨간색 배경 숫자(4,1)를 보자. CAPCA와 A 사이에 LCS는 1 이었다. 이 때 A에 C가 붙으면, LCS는 늘어난다. 왤까?
   • CAPC 하고 AC만 보더라도 이미 LCS가 2였기 때문에, 이걸 가져오면 되는 것이다.
3. 파란색 배경 숫자(4,2)를 보자. CAPCA와 AC 사이에 LCS는 2 이었다. 이 때 AC에 A가 붙으면, LCS는 늘어난다. 왤까?
   • 두 문자열의 마지막이 A로 일치하기 때문이다. 이 경우 두 문자열의 마지막 A가 없었을 경우의 LCS에 1 증가한 값이 될 것이다.
   • (4,1)이나 (3,2)는 볼 필요가 없다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class BOJ9251 {
 
    static String input1;
    static String input2;
    static int N;
    static int M;
    static int[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        input1 = bf.readLine();
        input2 = bf.readLine();
        N = input1.length();
        M = input2.length();
        dp = new int[N+1][M+1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < M + 1; j++) {
                if (input1.charAt(i-1) == input2.charAt(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[N][M]);
    }
}