9251번 풀이 (1) 썸네일형 리스트형 백준 9251번 LCS C/C++ 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 문제, 그 중에서도 2차 배열을 이용하면 쉽게 풀 수 있다. 각각의 string 글자 수를 가진 2차 배열을 만들어서 각각의 cell을 채워나간다. 각각의 글자가 같지 않을 때는 왼쪽이나 위(i나 j가 같은) 중에서 크기가 큰 열을 선택하고, 같은 상황이 온다면 왼쪽 위에서 1을 더한 뒤 왼쪽이나 위 열과 크기를 비교해서 합친다. string 입출.. 이전 1 다음