글 읽기 - 메모이제이션 시 string 배열을 쓰면 시간초과가 나는 이유를 모르겠습니다

shyne2496 1년 전 0

바로 string을 구할 수 있을 것이라 생각하고 일반 LCS코드를 변형하였는데

아래 코드에서 왜 시간초과가 나는지 잘 모르겠습니다.

제가 놓친 부분이 있으면 알려주시면 감사하겠습니다.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string A, B;
string cache[1001][1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> A >> B;
	for(int i=0; i<A.size()+1; i++){
		for(int j=0; j<B.size()+1; j++){
			if(i==0 || j==0){
				cache[i][j] = "";
				continue;
			}
			if(A[i-1]==B[j-1]){
				cache[i][j] = cache[i-1][j-1] + A[i-1];
			}
			else{
				if(cache[i-1][j].size() >= cache[i][j-1].size())
					cache[i][j] = cache[i-1][j];
				else
					cache[i][j] = cache[i][j-1];
			}
		}
	}
	
	if(cache[A.size()][B.size()].size()==0)
		cout << 0 << "\n";
	else{
		cout << cache[A.size()][B.size()].size() << "\n";
		cout << cache[A.size()][B.size()] << "\n";
	}
	
	return 0;
}

kidw0124 1년 전 5

string을 대입하는 과정에서 string문자열 길이만큼 시간을 잡아먹기 때문에 문자열 길이를 N이라고 하면 O(N^3)코드입니다. string에서 어차피 앞부분은 같기 때문에 추가되는 한문자와 위치만 저장하는 방식으로 푸시면 O(N^2)으로 시간초과 안날 것 같습니다

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

문제

문제

출처

ICPC

메모이제이션 시 string 배열을 쓰면 시간초과가 나는 이유를 모르겠습니다

shyne2496 1년 전 0

kidw0124 1년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말