[백준] 16500번 문자열 판별

16500번: 문자열 판별

문자열 S를 처음부터 탐색하면서

현재 idx부터 목록 A에 있는 단어가 포함돼 있으면

재귀 호출로 (idx+단어 길이)번째부터 목록 A에 있는 단어가 있는지 탐색한다.

 

이때 dp[idx]가 true면 이전에 이 idx부터 시작되는 단어를 탐색해봤다는 뜻이므로

굳이 또 계산할 필요 없이 return으로 돌아온다.

dp[idx]가 false면 처음 탐색한다는 뜻이므로 true로 바꿔주고 탐색하러 간다.

 

idx와 문자열 S의 길이가 같다면

성공이므로 1을 출력하고

함수가 끝날 때까지 idx가 문자열 S의 끝에 도달하지 못했다면

0을 출력한다.

 

이전에 푼 문제였는데 기억도 안 나고

코드를 보니까 풀이가 엉터리였다.

왜 통과했었는지 의문

지금도 dp 잘 모르겠어서 풀기 힘들었다.

나중에 다시 풀 땐 쉽게 풀리면 좋겠다.

#include <iostream>
#include <string>
using namespace std;
string S, A[101];
int N;
bool dp[101];
void solv(int idx) {
	if (idx == S.size()) {
		cout << 1;
		exit(0);
	}
	if (dp[idx]) return; // 체크되어 있으면 여기서부터 시작하는 문자열을 다 체크해봤다는 뜻이므로 탐색할 필요 없이 돌아온다
	dp[idx] = true;
	for (int i = 0; i < N; i++) {
		if (S.size() - idx < A[i].size()) continue;
		if (A[i] == S.substr(idx, A[i].size())) solv(idx + A[i].size());
	}
}
int main() {
	cin >> S >> N;
	for (int n = 0; n < N; n++) cin >> A[n];
	solv(0);
	cout << 0;
	return 0;
}