[성실코딩 5일차] 백준 #5582 공통 부분 문자열 / DP *

완전탐색으로 풀었다가 당연히 시간초과 났구요~~~~ 라라랄랄라라라

DP 문제인거 알았지만 어떻게 구현할 수 있을지 감이 안잡혀서 완탐으로 시도해봤숩니당~~

틀린코드 => 시간초과

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> // min()

using namespace std;

string s1;
string s2;

vector<int> max_str_size;

// s1_start_idx, s2_start_idx
int count(int s2_s_i, int s1_s_i) {

	int res = 0;

	int s2_idx = s2_s_i;
	int s1_idx = s1_s_i;

	while (s1_idx <s1.size() && s2_idx<s2.size()) {
		if (s1[s1_idx] != s2[s2_idx]) {
			break;
		}
		res++;
		s1_idx++;
		s2_idx++;
	}
	return res;
}

// start_idx : s2의 부분집합 시작 위치
int getMaxStr(int start_idx, int s2_start_idx) { 

	// 검사할 필요 없음
	// 이전에 검사를 해봤는데 start_idx의 알파벳이 s1 존재하지 않음
	if (max_str_size[start_idx]==0) {
		return 0;
	}

	int idx = start_idx;

	int res = 0;
	int max = 0;
	for (int i = s2_start_idx; i < s1.size(); i++) {
	
		if (s2[idx]==s1[i]) { // 문자가 같을 경우
			res = count(idx,i);
		}
		else { // 다를 경우
			// 초기화
			res = 0;
			idx = start_idx;
		}
		// max update
		if (max<res) {
			max = res;
		}
	}

	// * MAX UPDATE를 FOR문 안에 ELSE 구문에 들어가 있었음 * 
	// 모든 문자열이 같을 경우
	// for문 안에서 else구문에 들어가지 못하기 때문에
	// max를 update해주지 못한다.

	return max;
}

int main(void) {

	cin >> s1;
	cin >> s2;

	int size= s2.size();
	max_str_size.assign(size, -1); // -1로 초기화

	int res_max = 0;
	for (int i = 0; i < size; i++) {
		int temp =getMaxStr(i,0);
		if (max_str_size[i] < temp) { // 업데이트
			max_str_size[i] = temp;
		}
		if (res_max << temp) { // 최종적으로 가장 긴 공통 부분 문자열 길이
			res_max = temp;
		}
	}

	cout << res_max << endl;

	return 0;
}

---

 참조해서 공부한 코드 링크 : http://wootool.tistory.com/179

이 분 코드 깔끔함!! 바로 이해감!

입력으로 아래와 같이 들어온 경우, 문제 풀이.

ABRACADABRA

ECADADABRBCRDARA

(아무 숫자 안적혀 있고 빈 칸은 0이다! 생략했음)

DP 처리하는 2차원 배열 생성

DP[i][j] = str1의 i, str2의 j까지의 공통 부분 문자열의 최대 길이를 저장하고 있다. 

따라서 i와 j에 같은 문자(알파벳)이 들어온 경우, 이전까지의 최대길이 (dp[i-1][j-1] ) 에 +1을 해준다.