[백준] 9251 LCS - Dynamic Programming / Java

• 문제 링크

9251번: LCS

 

• 풀이 과정

LCS(최장 공통 부분 수열) 을 구할 두 문자열을 입력받고,

각각의 문자열의 길이 + 1 을 행과 열의 크기로 갖는 2차원 dp 배열을 생성한다.

 

dp 배열을 모두 탐색하며 해당 좌표에 상응하는 두 문자가 같은 지 비교한다.

같다면 이전에 저장된 값(현재까지의 최장 공통 부분 수열 길이) 에 + 1 수행 후 저장하고,(dp[i - 1][j - 1] + 1)

다르다면 현재까지 저장된 최장 공통 부분 수열 길이 중 큰 값을 저장한다. (Math.max(dp[i - 1][j], dp[i][j - 1]))

 

이러한 과정을 거친 후 구해지는 dp 배열의 모습은 아래와 같다.(0번째 인덱스 제외)

 

dp	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	3	3	3	4

따라서 dp[row][col] 이 두 문자열의 최장 공통 부분 수열 길이가 되며 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String a = br.readLine();
        String b = br.readLine();

        int row = a.length();
        int col = b.length();
        int[][] dp = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (a.charAt(i - 1) == b.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]);
            }
        }

        bw.write(String.valueOf(dp[row][col]));
        bw.flush();
    }

}