[백준 9251번] LCS

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

 

 

package bra;

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

public class Bra9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

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

    }
}

 

 

이번 문제는 공포의 DP 문제이다. 어려울줄 알았는데 표를 그리면 빨리 파악할 수 있는 문제이다. 

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	0	1	1	2	2	2
A	0	1	1	2	3	3
Y	0	1	1	2	3	3
K	0	1	1	2	3	4
P	0	1	1	2	3	4(이거 출력)

 

이렇게 표를 정리하면 숫자가 증가하는 부분을 확인할 수 있다. 즉, 문자가 같을 때는 숫자를 증가시키고, 다를 경우에는 이전 행과 바로 위에 있는 이전 열의 값을 비교하여 더 큰 값을 선택하면 된다. 비교적 간단한 문제이다.