[BackJoon]9251번, LCS(Longest Common Subsequence)

문제

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

 

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

 

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

풀이

 

조금 헷갈리지만 일단은 동적 계획법 문제이다.

 

그걸 몰랐으면 순열로 모든 부분수열을 순회하려고 했을 것 같다.

 

문제를 보고 이게 뭘로 풀 때 더 효율적인 유형인가 판단하는 것도 능력일 듯.

 

어쨌거나 주어진 두 문자열에 대해서 각각 처음부터 끝까지 순회하며 2차원 배열에 현재까지의 최장 길이를 입력한다.

 

순회를 끝까지 마친 뒤에 마지막 값을 출력하면 되는, 간단하다면 간단한 문제이다.

 

하지만 2차원 배열을 다루어야 하고, 이는 두 문자열의 길이를 곱한 것 만큼의 요소를 다루어야 한다는 뜻이다.

 

오랜 시간에 걸쳐 고치고 고치며 통과했지만, 코드는 이전 동적계획법 문제에서 거의 벗어나지 않아 조금 약이 올랐다.

 

어쨌거나 코드.

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

public class Prob9251 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String n = br.readLine();
		String m = br.readLine();

		int[][] memo = new int[n.length() + 1][m.length() + 1];

		for (int i = 1; i <= n.length(); i++) {
			for (int j = 1; j <= m.length(); j++) {
				if (n.charAt(i - 1) == m.charAt(j - 1)) {
					memo[i][j] = memo[i - 1][j - 1] + 1;
				} else {
					memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
				}
			}
		}

		System.out.println(memo[n.length()][m.length()]);
	}
}