위 문제는 백준 사이트의 알고리즘 9251 문제에 관한 설명입니다.

문제

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

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str1 = sc.nextLine();
		String str2 = sc.nextLine();
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
		for (int x = 1; x <= str1.length(); x++) {
			char c1 = str1.charAt(x - 1); 
			for (int y = 1; y <= str2.length(); y++) {
				char c2 = str2.charAt(y - 1); 
				if (c1 == c2) {
					dp[x][y] = dp[x - 1][y - 1] + 1;
				} else {
					dp[x][y] = Math.max(dp[x - 1][y], dp[x][y - 1]);
				}
			}
		}
		System.out.println(dp[str1.length()][str2.length()]);
	}
}

#include<cstdio>
#include<algorithm>
using namespace std;
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = max({ dp[i][j - 1], dp[i - 1][j],
                             dp[i - 1][j - 1] + (s1[i] == s2[j]) 
                           });
    printf("%d", dp[i - 1][j - 1]);
    return 0;
}

string 1과 2에 각 문자열을 넣고 c1에 str1번, c2에 str2번의 단어 하나씩을 선정해서 비교합니다.

만약 같다면 좌측 대각선의 값을 +1 시킵니다.

그렇지 않다면 좌측과 상단의 값중 더 큰값을 넣는 것입니다.

LCS