[백준] 9251 - LCS

1. 문제

9251번: LCS

2. 개요

두 문자열 사이의 공통 부분 문자열들 중 가장 긴 문자열의 길이를 구하는 DP문제.

3. 풀이 및 코드

3-1. 풀이

예제의 두 문자열을 각각 s1, s2라고 하고 이 둘의 문자들을 각각 행, 열로 하는 표를 만들어보자.

	C	A	P	C	A	K
A
C
A
Y
K
P

s1의 첫 문자인 A부터 시작한다.

이때 비교는 각각 하나의 문자와 하는 것만이 아니라 해당 부분까지의 문자열과도 대조한다.

즉, “A” 와 “C”, “A”와 “CA”, “A”와 “CAP” … 같은 식이다.

따라서 첫번째 행은 아래와 같이 채워지게 된다.

	C	A	P	C	A	K
A	0	1	1	1	1	1
C
A
Y
K
P

두 번째 행으로 넘어가 살펴보자.

일단 동일한 C를 만났으므로 +1 한다.

다음으로 A를 만났을 때, 이때는 C ≠ A이므로 결과에 영향이 없다.

따라서 지금 행할 CA - AC의 전 단계 중 가장 큰 값을 기대할 수 있는 CA - A나 AC - C의 LCS인 dp테이블의 왼쪽, 위쪽 중 더 큰 값이 값으로 들어가게 된다.

다음으로 네번째 C를 만날 때 인데, 이때는 CAP - A까지의 결과에 둘 다 C를 붙인 상황이다.

따라서 테이블 상 왼쪽 위의 값 +1 이 값으로 들어가게 된다.

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2
A
Y
K
P

계속해서 표를 완성하면 다음과 같은 결과를 얻을 수 있다.

	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

3-2. Python

import sys

s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()
dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]

for i in range(len(s1)):
    for j in range(len(s2)):
        if s1[i] == s2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

print(dp[-1][-1])

3-3. C#

static void Main(string[] args)
{
    char[] s1 = Console.ReadLine().ToCharArray();
    char[] s2 = Console.ReadLine().ToCharArray();

    int[,] dp = new int[s1.Length + 1, s2.Length + 1];

    for (int i = 0; i < s1.Length; i++)
    {
        for (int j = 0; j < s2.Length; j++)
        {
            if (s1[i] == s2[j])
                dp[i + 1, j + 1] = dp[i, j] + 1;
            else
                dp[i + 1, j + 1] = Math.Max(dp[i + 1, j], dp[i, j + 1]);
        }
    }

    Console.WriteLine(dp[s1.Length, s2.Length]);
}