[C++] 백준 9251: LCS

https://www.acmicpc.net/problem/9251

 

모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.

이 문제의 경우 DP를 사용하면 편하게 풀 수 있다!

 

 

<풀이>

자, DP이므로 배열의 의미를 잘 지정하는 것이 중요하다.

 

어떤 식으로 배열을 설정하면 좋을까?

이 문제는 i와 j에 각각 문자열의 문자를 대입시키고

dp[i][j]의 값으로 두 문자열의 LCS를 지정하면 된다.

 

이 문제를 풀어보지 않았다면 i와 j에 이런 식으로 대입시키는 건 생각 못했을 거 같다.

 

 

<점화식>

그럼 점화식은 어떻게 구할까?

dp의 경우 논리적으로 사고하기 어렵다면 시뮬레이션을 돌려보는 것이 크게 도움이 되는 경우가 많다.

이 문제도 같은 경우이다.

 

먼저 예제의 ACAYKP를 i에, CAPCAK를 j에 대입시킨다고 하자.

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

 

먼저 A와 CAPCAK를 비교하자.

C:    LCS: 0

CA: A   LCS: 1

CAP: A   LCS: 1

CAPC: A   LCS: 1

CAPCA: A   LCS: 1

CAPCAK: A   LCS: 1

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

 

다음으로 AC와 CAPCAK를 비교해보자.

C: C   LCS: 1

CA: C or A   LCS: 1

CAP: C or A   LCS: 1

CAPC: AC   LCS: 2

CAPCA: AC   LCS: 2

CAPCAK: AC   LCS: 2

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2	2	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

강조된 부분들의 특징이 보이는가?

문자열 1의 문자와 문자열 2의 문자가 같을 때, 왼쪽 대각선 위의 값에서 +1한 값이 LCS값이 되는 것이 보인다!!!

 

그럼 같지 않을 경우는 어떨까?

배열에서 왼쪽이나 위쪽 중 최댓값이 배열의 값이 된다.

 

LCS에 대한 더 자세한 설명이 궁금하다면 그림으로 너무나도 잘 설명해주신 분의 벨로그를 참조해보자.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring

 

이걸 코드로 표현하면 다음과 같다.

#include <iostream>
using namespace std;

int dp[1005][1005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s1, s2;
    cin>>s1>>s2;

    s1 = " " + s1;
    s2 = " " + s2;

    int leng1 = s1.length();
    int leng2 = s2.length();

    for(int i = 1; i < leng1; i++){
        for(int j = 1; j < leng2; j++){
            if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout<<dp[leng1-1][leng2-1];
    return 0;
}

여기서 s1과 s2에 각각 공백을 앞에 더해주는 걸 눈치챘는가?

이는 0부터 시작할경우 i-1, j-1을 참조하며 out of range 에러가 발생할 수 있기 때문이다.

이런 사소한 디테일도 알고리즘을 하며 익혀나가는 중요한 부분인 것 같다.