백준 16500번 문자열 판별

문제 링크입니다: https://www.acmicpc.net/problem/16500

16500번: 문자열 판별

오랜만에 풀어보는 DP 문제였습니다.

가지치기만 적당히 해준다면 쉽게 풀 수 있는 문제입니다.

 

알고리즘은 아래와 같습니다.

1. S 문자열 idx번째 인덱스부터의 부분문자열이 A에 포함된 단어 중 하나와 일치하는지를 확인합니다.

2. 일치한다면 (idx + 부분문자열의 길이) 번째부터의 부분문자열이 또 A에 포함된 단어 중 하나와 일치하는지를 확인합니다.

3. 위 과정을 반복하다가 S 문자열의 끝까지 도달한다면 A의 단어들로 S를 공백없이 구성할 수 있기 때문에 1 즉, true를 출력해줍니다.

 

* 주의할 점은 S 문자열의 길이를 초과하면 안된다는 점입니다!

 

	#include <iostream>
	#include <string>
	#include <cstring>
	using namespace std;
	const int MAX = 100;
	string S;
	int N;
	string words[MAX];
	int cache[MAX];
	bool func(int idx)
	{
	if (idx == S.length())
	{
	return true;
	}
	int &result = cache[idx];
	if (result != -1)
	{
	return result;
	}
	result = 0;
	for(int i = 0; i < N; i++)
	{
	if (S.length() < words[i].length() + idx)
	{
	continue;
	}
	bool flag = true;
	for (int j = 0; j < words[i].length(); j++)
	{
	if (S[idx + j] != words[i][j])
	{
	flag = false;
	break;
	}
	}
	if (flag)
	{
	result |= func(idx + words[i].length());
	}
	}
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> S;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
	cin >> words[i];
	}
	memset(cache, -1, sizeof(cache));
	cout << func(0) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~