[BAEKJOON]9251 LCS

문제 요약

• 알고리즘 분류: dp
• 난이도: Gold5
• 문제내용:
  • 두 문자열에서 가장 긴 수열 길이를 구하여라
• 사이트: https://www.acmicpc.net/problem/9251

9251번: LCS

문제풀이

 이번 문제에는 동적계획법 알고리즘 대표적인 문제인 LCS이다. LCS에 대한 개념은 아래 사이트에서 확인해보면 된다.

https://jih3508.tistory.com/191

[알고리즘 이론] LCS(Longest Increasing Subsequence) 최장 증가 부분 수열

 위에 대한 내용 개념을 제대로 알면 문제 푸는데는 지장 없을거라고 생각한다.

Code

Python

X = input()
Y = input()
xLenth = len(X)
yLenth = len(Y)

dp = [[0] * (yLenth + 1) for _ in range(xLenth + 1)]

for i in range(1, xLenth + 1):
    for j in range(1, yLenth + 1):
        if X[i - 1] == Y[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[xLenth][yLenth])

Java

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

public class Main {
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] X = br.readLine().toCharArray();
		char[] Y = br.readLine().toCharArray();
		
		int xLegth = X.length;
		int yLegth = Y.length;
		
		int[][] dp =  new int[xLegth + 1][yLegth + 1];
		Arrays.stream(dp).forEach(array -> Arrays.setAll(array, x -> 0));
		
		for(int i = 1; i <= xLegth; i++) {
			for(int j = 1; j <= yLegth; j++) {
				if(X[i - 1] == Y[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[xLegth][yLegth]);
			
	}
	
}