[백준] 9251 LCS, python, C++

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

9251번: LCS

동적 계획법을 사용한 문제인데 어떻게 짜야할지 막막했다. 그래서 구글링으로 LCS에 대해서 찾아보았고, 도움받은 것을 바탕으로 코드를 작성했다. 맨 아래 참고 블로그를 확인하자

a, b = input(), input()
c, r = len(a), len(b)
t = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
for rr in range(r):
    for cc in range(c):
        if a[cc] == b[rr]:
            t[rr+1][cc+1] = max(t[rr + 1][cc], t[rr][cc + 1], t[rr][cc] + 1)
        else:
            t[rr+1][cc+1] = max(t[rr+1][cc], t[rr][cc+1])

print(t[r][c])

 

#include<iostream>
#include<vector>
using namespace std;

#define max(x,y) (x > y) ? x : y

int main() {
	string a, b;
	cin >> a >> b;
	vector<vector<int>> t(b.length() + 1, vector<int>(a.length() + 1, 0));
	for (int i = 0; i < b.length(); i++)
	{
		for (int j = 0; j < a.length(); j++) {
			t[i + 1][j + 1] = max(t[i + 1][j], t[i][j + 1]);
			if (a[j] == b[i])
				t[i + 1][j + 1] = max(t[i + 1][j + 1], t[i][j] + 1);
		}
	}
	cout << t[b.length()][a.length()] << '\n';

	return 0;
}

 

 

---

참고

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence