백준 9521번: LCS

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

9251번: LCS

 

 

0. 알고리즘 분류

 다이나믹 프로그래밍

 

 

1. 문제

 

 

2. 풀이

 LIS(가장 긴 증가하는 부분 수열) 문제와 비슷한 유형인줄 알고 시도했다가 제대로 대가리 깨졌다. 문제의 개념은 비슷할지마도 사용하는 알고리즘은 완전히 다르다. 몰라서 역시 구글링했다. http://melonicedlatte.com/algorithm/2018/03/15/181550.html

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

생전 처음보는 문제 유형이었다...

 

 

3. 코드

#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;
}