글 읽기 - 97퍼에서 시간초과 뜹니다 ㅠㅠ

gs25 2년 전 0

다른 시간초과글을 보고 dp 크기를 1000보다 크게 설정해줬음에도 97퍼에서 시간초과 뜹니다. 도움 부탁드립니다.. ㅜㅜ

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

string arr1;
string arr2;

string dp[1050][1050] = {};

string LCS(int l1, int l2) {
	if (l2 == 0 || l1 == 0) return "";
	if (dp[l1][l2].length()) return dp[l1][l2];
	
	string& re = dp[l1][l2];

	if (arr1[l1 - 1] == arr2[l2 - 1]) {
		//std::cout << arr1[l1 - 1];
		return re = LCS(l1 - 1, l2 - 1).append(1, (arr1[l1 - 1]));
	}
	string tmp = LCS(l1, l2 - 1);
	string tmp2 = LCS(l1 - 1, l2);
	return re = (tmp.length() > tmp2.length()) ? tmp : tmp2;

}

int main(void) {
	
	getline(cin, arr1);
	getline(cin, arr2);
	string s = LCS(arr1.length(), arr2.length());
	std::cout << s.length();
	if(s.length()) cout << "\n" << s;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

97퍼에서 시간초과 뜹니다 ㅠㅠ

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말