백준 16500 문자열 판별

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 문자열 S가 주어지고 N개의 줄에 N개의 문자열이 주어질 때 이 N개의 문자열을 이용해서 S를 만들 수 있는지 여부를 판단하는 문제입니다.

 

dp를 이용하여 해결하여야 하는 문제입니다. 1차원 배열 dp를 선언해주고

dp[pos] = pos위치에서부터 남은문자열을 만들 수 있는지 없는지를 의미합니다.

 

따라서 함수를 하나 선언하고 현재 pos위치에서부터 N개의 문자열중 동일하게 매칭되는 문자열이 있을 경우 위치를 이동하여 계속 진행해 주면 됩니다. 이 문제에서 dp를 이용하는 이유는 문자열을 만들 수 없는지를 체크하는 경우에 dp를 사용하지 않으면 영겁의 시간이 걸리게 됩니다. 예를들어 aaaaaaaaaaaaaaab 가 S이고 100개의 a가 있는 경우를 생각해보시면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <string>
#include <string.h>

using namespace std;

string S;
int N;
string A[101];
int len[101];
int ans;
int cache[101];

int search(int pos) {
	
	int &ret = cache[pos];
	if(ret != 0) return ret;
	
	if(pos == S.size()) 
		return ret = 1;

	for(int j = 0; j < N; j++) {
		bool flag = false;	
		for(int i = 0; i < len[j]; i++) {
			if(A[j][i] != S[pos+i])
				flag = true;
		}
		if(!flag)
			ret |= search(pos+len[j]);
	}
	
	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> S >> N;
	for(int i = 0; i < N; i++) {
		cin >> A[i];
		len[i] = A[i].size();
	}
	cout<<search(0);
	
	return 0;
}