[백준] 9251번 : LCS [C/C++]

#문제

9251번: LCS

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

9251번: LCS

 

---

#접근방법

이전 배열의 값을 이용하는 동적계획법으로 접근하면 된다.

반응형

---

#풀이

 

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int arr[1005][1005];

int main(){
	string a,b;
	int ans = 0;
	
	cin >> a >> b;
	
	for(int i=1;i<=a.size();i++)
		for(int j=1;j<=b.size();j++)
			if(a[i-1]==b[j-1])
				arr[i][j] = arr[i-1][j-1] + 1;
			else
				arr[i][j] = max(arr[i-1][j],arr[i][j-1]);
	
	printf("%d",arr[a.size()][b.size()]);
	
	return 0;
}

LCS의 로직은 아래와 같다.

1. 문자열a,b의 한 글자씩 비교한다.
2. 두 문자가 다르다면 arr[i-1][j]와 arr[i][j-1]중에 큰 값을 표시한다.
3. 두 문자가 같다면 arr[i-1][j-1]값에 +1을 한다.
4. 위 과정을 반복한다.

부분수열은 연속된 값이 아니다. 따라서 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지가 된다. 현재의 문자를 비교하는 과정 이전의 과정이 바로 arr[i-1][j]와 arr[i][j-1]가 된다.

 

두 문자가 같으면 지금까지의 최대 공통 부분수열에 1을 더해주면 되므로 arr[i-1][j-1]에 1을 더해준다.

 

마지막 배열 arr[a.size()][b.size()]을 출력하면 정답이다.

---

#성능

---

#정리

LCS의 알고리즘 로직을 알고 있고 이를 구현할 수 있으면 풀 수 있는 문제였다.