문제풀이/백준
9251 - LCS
동바리
2021. 9. 11. 21:20
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
문제 :
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이참고 :
http://melonicedlatte.com/algorithm/2018/03/15/181550.html
[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect
출처 : https://www.acmicpc.net/problem/9251 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB76453240240041.746% 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때,
melonicedlatte.com