백준 2195 문자열 복사 c++

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

2195번: 문자열 복사

#include <iostream> //메모리초과
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>
#include <climits> // int32max

using namespace	std;

string s, p;
unordered_set<string> sett;
int cnt = 0, res = 2147483647;

void	dfs(int depth) {
	if (depth == p.size()) { // 다만들었을때
		res = min(res, cnt);
		return ;
	}
	for (int i = 1; depth + i <= p.size(); i++) {
		if (sett.find(p.substr(depth, i)) != sett.end()) { // can copy
			cnt++;
			dfs(depth + i);
			cnt--;
		}
	}
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> s >> p;

	for (int i = 0; i < s.size(); i++)
		for (int j = 1; i + j <= s.size(); j++)
			sett.insert(s.substr(i, j));
	dfs(0);
	cout << res;
}

나올 수 있는 모든 가짓수 string set에 등록해주고, dfs 돌면서 모든 경우 탐색했다. 메모리 초과;  메모리가 안되니 그때그때 검색해서 처리해주자.

#include <iostream> //시간초과
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>
#include <climits> // int32max

using namespace	std;

string s, p;
int cnt = 0, res = 2147483647;

bool canCopy(string str) {
	for (int i = 0; i + str.size() <= s.size(); i++)
		if (s.substr(i, str.size()) == str)
			return true;
	return false;
}


void	dfs(int depth) {
	if (depth == p.size()) { // 다만들었을때
		res = min(res, cnt);
		return ;
	}
	for (int i = 1; depth + i <= p.size(); i++) {
		if (canCopy(p.substr(depth, i))) {
			cnt++;
			dfs(depth + i);
			cnt--;
		}
	}
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> s >> p;

	dfs(0);
	cout << res;
}

이러니까 시간초과 난다; 

생각해보니 하나씩 짜르면 무조건 다 만들 수 있어서 그냥 제일 긴 문자열 그 idx에서 찾아서 copy하면 된다.

#include <iostream> // 시간초과
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;

string s, p;

bool canCopy(int startIdx, int len) {
	for (int i = 0; i + len <= s.size(); i++) {
		for (int j = 0; j < len; j++) {
			if (s[i + j] != p[startIdx + j])
				break ;
			if (j == len - 1)
				return true;
		}
	}
	return false;
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> s >> p;
	int idx = 0, len = p.size(), cnt = 0;

	while (idx < p.size()) {
		if (canCopy(idx, len)) {
			cnt++;
			idx += len;
			len = p.size() - idx + 1;
		}
		len--;
	}
	cout << cnt;
}

substr 하는 부분다 인덱스 하나하나 비교하는 걸로 바꿔주니까 통과했다. 비교군이 엄청 많으니까 유의미한 차이가 난다.

#include <iostream> // 통과
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>
#include <utility>

using namespace	std;

string s, p;

bool canCopy(int startIdx, int len) {
	for (int i = 0; i + len <= s.size(); i++) {
		for (int j = 0; j < len; j++) {
			if (s[i + j] != p[startIdx + j])
				break ;
			if (j == len - 1)
				return true;
		}
	}
	return false;
}

int	main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> s >> p;
	int idx = 0, len = p.size(), cnt = 0;

	while (idx < p.size()) {
		if (canCopy(idx, len)) {
			cnt++;
			idx += len;
			len = p.size() - idx + 1;
		}
		len--;
	}
	cout << cnt;
}