[백준(BOJ)] 9251번 : LCS - C++[CPP]

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

9251번: LCS

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

 

---

 

⊙ 문제 접근 과정

 

LCS 알고리즘 문제다. LCS는 번역하면 최장 공통 부분 문자열이다.

전에 다뤘던 LIS 최장 증가 부분 수열과 유사하다.

 

LIS는 다이나믹 프로그래밍(DP)을 기반으로 알고리즘이 구성되어있는데 LCS도 마찬가지이다.

DP를 이용하여 구현하면 공통 부분 수열의 길이를 구할 수 있다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;

string st1, st2;
int dp[1001][1001];


int main() {
    cin >> st1 >> st2;

    int len1= st1.size();
    int len2= st2.size();
	
    for(int i=1; i<=len2; i++) {
		for (int j = 1; j <= len1; j++) {
			if (st2[i - 1] == st1[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
    }
	cout << dp[len2][len1];
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!