https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net

[ 문제풀이 ]
LCS란 Longest Common Subsequence 즉, 최장 공통부분 수열을 찾는 것입니다. 이 문제는 모든 수열의 부분수열 중에서 공통이 되는 가장 긴 수열의 길이를 구하는 문제입니다.
가장 긴 수열을 찾기 위해서는 각 수열의 요소들을 하나씩 비교해서 만약 같다면 바로 전의 최장 수열 길이의 최댓값에 +1을 해주고 같지 않다면 이전의 최장 수열 길이 중 최댓값을 대입해주면 됩니다.
이해하기 쉽게 다음 두 수열을 예로 들어서 설명하겠습니다.
ACAYKP
CAPCAK
먼저 문자열의 최대 길이는 1000이므로 dp[ 1001 ][ 1001 ]의 배열을 만들어줍니다. 그리고 각각의 값들을 비교하면서 위에서 설명한 대로 값들을 대입합니다. 쉬운 비교를 위해서 모든 수열의 0번째 요소를 1번으로 설정합니다.

다음으로 각 요소들을 비교해가면서 서로 같은 문자라면 dp [ i - 1 ][ j - 1 ] + 1의 값을 대입해줍니다.
그렇지 않다면 바로 직전까지의 수열의 최댓값 즉, dp[dp [ i - 1 ][ j ]와 dp [ i ][ j - 1 ] 중 더 큰 값을 대입해줍니다.
먼저 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 1 ]인 'C'는 서로 다르기 때문에 dp [ 0 ][ 1 ]과 dp [ 1 ][ 0 ]중 더 큰 값을 dp [ 1 ][ 1 ]에 대입해줍니다.
다음으로 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 2 ]인 'A'는 서로 같으므로 dp [ 0 ][ 1 ] + 1을 dp [ 1 ][ 2 ]에 대입해줍니다. 이런 식으로 쭉 대입을 해주다 보면 다음과 같은 표가 완성됩니다.

그리고 마지막에 dp[ 6 ][ 6 ]을 출력해주면 가장 긴 부분 수열의 길이를 구할 수 있습니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <iostream> #include <string> using namespace std; int dp[1001][1001]; int main() { string str[2]; for (int i = 0; i < 2; i++) { cin >> str[i]; str[i] = '0' + str[i]; //수열을 1부터 시작하기 위해서 맨 앞에 더미 문자를 넣음 } for (int i = 1; i < str[0].size(); i++) { for (int j = 1; j < str[1].size(); j++) { //각 문자들을 비교하며 최장 부분수열의 길이를 경신 if (str[0][i] == str[1][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[str[0].size() - 1][str[1].size()-1]; } | cs |
'백준' 카테고리의 다른 글
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++) (0) | 2022.06.04 |
---|---|
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++) (0) | 2022.06.03 |
[ 백준 ] 15686번 - 치킨 배달 (C++) (0) | 2022.06.01 |
[ 백준 ] 1149번 - RGB거리 (C++) (0) | 2022.05.31 |
[ 백준 ] 1799번 - 비숍 (C++) (0) | 2022.05.30 |