[알고리즘 / 백준] 9251 - LCS

www.acmicpc.net/problem/9251

9251번: LCS

 

문제는 위와 같으며 각 문장을 단어로 쪼개서 하나씩 단어를 늘려가면서 부분 수열의 수를 구하는 방식으로 문제를 해결할 수 있습니다.

 

예제를 테이블을 이용해 살펴보면 다음과 같습니다.

 

A 문장이 ACAYKP 이고 B 문장이 CAPCAK 인 경우 각 문장을 단어로 쪼개서 이중 for 문을 돌면서 서로 비교합니다.

 

1. 예를 들어 A 문장의 ACAY 와 B 문장의 CAP 를 비교한다고 하면 마지막 단어인 Y 와 P 가 서로 다르기 때문에 (ACA 와 CAP 의 부분 수열 수)와 (ACAY 와 CA 의 부분 수열 수) 중 더 큰 값을 ACAY 와 CAP 의 부분 수열 수(2)로 저장합니다.

 

2. 다음으로 A 문장의 ACAYK 와 B 문장의 CAP 를 비교한다고 하면 마지막 단어인 K 와 P 가 서로 다르기 때문에 (ACAY 와 CAP 의 부분 수열 수)와 (ACAYK 와 CA 의 부분 수열 수) 중 더 큰 값을 ACAYK 와 CAP 의 부분 수열 수(2)로 저장합니다.

 

3. 마지막으로 A 문장의 ACAYKP 와 B 문장의 CAP 를 비교한다고 하면 마지막 단어가 P 로 동일하기 때문에 (ACAYK 와 CA 의 부분 수열 수) 에 + 1 을 한 값(3)을 저장합니다.

 

이렇게 이중 for 문을 모두 돌고 나면 가장 마지막에 처음 주어진 두 문장의 최대 부분 수열 수를 알 수 있게 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

stringA = stdin.readline().strip()
stringB = stdin.readline().strip()

result = [[0] * (len(stringA) + 1) for _ in range(len(stringB) + 1)]
for i in range(1, len(result)):
    for j in range(1, len(result[i])):
        if stringB[i - 1] != stringA[j - 1]:
            result[i][j] = max(result[i - 1][j], result[i][j - 1])
        else:
            result[i][j] = result[i - 1][j - 1] + 1

print(result[-1][-1])

 

자바 코드는 다음과 같습니다.

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

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

        String stringA = br.readLine();
        String stringB = br.readLine();
        int[][] result = new int[stringB.length() + 1][stringA.length() + 1];

        for (int i =  1; i < result.length; i++) {
            for (int j = 1; j < result[i].length; j++) {
                if (stringB.charAt(i - 1) != stringA.charAt(j - 1)) {
                    result[i][j] = Math.max(result[i - 1][j], result[i][j - 1]);
                } else {
                    result[i][j] = result[i - 1][j - 1] + 1;
                }
            }
        }

        System.out.println(result[stringB.length()][stringA.length()]);
    }
}