BOJ-9251
09 Sep 2021지난번에 틀렸던 LCS 문제를 다시 풀어봤다… 데이터 규모가 커지면 저장되는 메모리 위치도 중요하다는 점을 깨달았다. 이 부분을 정리해두면 좋을 것 같다
#include <bits/stdc++.h>
using namespace std;
char st1[1001], st2[1001];
int sub[1001][1001];
int max(int a, int b) {
return (a>b) ? a : b;
}
int lcs(char* st1, char* st2, int st1Len, int st2Len) {
for (int i=0; i<=st1Len; i++) {
for (int j=0; j<=st2Len; j++) {
if (i == 0 || j == 0)
sub[i][j] = 0;
else if (st1[i-1] == st2[j-1])
sub[i][j] = sub[i-1][j-1] + 1;
else
sub[i][j] = max(sub[i-1][j], sub[i][j-1]);
}
}
return sub[st1Len][st2Len];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> st1 >> st2;
cout << lcs(st1, st2, strlen(st1), strlen(st2)); // string은 str.length() / char[]는 strlen(str)
return 0;
}
// 전역변수는 메모리 힙 영역에, 지역변수는 스택 영역에 저장되기 때문입니다 int 100만개짜리 배열이면 4MB인데 보통 스택의 크기를 초과하게 됩니다
