백준 9251 LCS c++ [컴공과고씨]

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

9251번: LCS

이런 문제의 경우 각 경우 마다 최적의 경우의 수를 선택하면서 가면 된다.

저런식으로 각 자리를 늘려가면서 A에서 C가 들어갔을 때 LCS의 경우 0 AC와 C의 LCS = 1 이런식으로 표를 채워가준다. 중요한 것은 LCS가 하나 더 늘어나는 경우는 문자가 들어갈 수 있을 때 예를 들면 ACAYK 와 CAP 다음 순서에 ACAYKP 와 CAP가 나온다. P가 들어갈 수 있으므로 LCS는 하나 늘어날 수 있다. 중요한 것은 그 위 ACAYK 와 CA LCS에서 +1을 해주어야한다. (왼쪽 대각선 방향) 이유는 바로 왼쪽의 경우 이미 P가 그 전에 넣어진 LCS를 포함하기 때문이다.

그렇기 때문에 만약 양 문자가 같다면 dp[i][j] = dp[i-1][j-1] + 1 만약 다르다면 왼쪽 혹은 위쪽에서 더 값이 높은 것을 선택해주면된다. dp[i][j] = dp[i-1][j], dp[i][j-1] 둘 중 더 큰 것.

 

전체코드

#include <iostream>
#include <string>
using namespace std;
int dp[1002][1002];
int mx(int a, int b){
    return a > b ? a : b; // 삼항 연산자
}
int main(){  
    string s1;
    string s2;
    cin >> s1 >> s2;
    dp[0][0] = 0;
    for (int i = 0; i <= s1.length(); i++){
        dp[i][0] = 0;
    } for (int i = 0; i <= s2.length(); i++){
        dp[0][i] = 0;
    }
    for (int i = 1; i <= s1.length(); i++)
    {
        for (int j = 1; j <= s2.length(); j++)
        {
            if (s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                // 문자열이 같아 lcs하나 늘려줌
            }
            else
            {
                dp[i][j] = mx(dp[i][j - 1], dp[i - 1][j]);
                //둘 중 더 큰 거 선택
            }
        }
    }
    cout << dp[s1.length()][s2.length()];
    return 0;
 
} //1.5h

체감난이도	걸린시간	참고	사용 알고리즘
중	1.5h	옛날 알고리즘 다이나믹 프로그래밍 공부한 ppt 참고 최적의 경우를 선택하는 경우에 대한 아이디어가 가물가물해서 옛날에 공부했던 DNA 염기서열 찾기를 보며 다시 공부한 후 풀었음	다이나미 프로그래밍 (dynamic programming)