백준 BOJ 16500 - 문자열 판별

아니 이게 왜 뇌절

오열

 

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

16500번: 문자열 판별

처음에 그냥 문자열 길이 긴순으로 적당히 나눠보려했는데

aaaaaaaa 뭐 이런 테스트케이스보고 안될거같다고 깨달아버림

dp[k] 를 k-1번째 인덱스까지 문자열을 A에 포함되는 문자열로 만들수 있는지 여부로 정합시다.

그럼 다음 A.length() 개 문자가 서로 똑같을때 dp[k+A.length()] = 1 로 만들어 줄 수 있겠지요

이 과정을 반복해서 dp[s.length()] 를 만들수 있는지 여부를 체크해주면 AC.

 

ㄹㅇ 이걸왜 뇌절쳤지

나병

#include <bits/stdc++.h>
using namespace std;

vector<string> v;

bool chk[1234] = {0}; 

bool cmp(const string &a, const string &b){
	return a.length()>b.length();
}

int main(){
	string s,tmp;
	cin >> s;
	
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> tmp;
		v.push_back(tmp);
	}
	
	sort(v.begin(), v.end(), cmp);
	
	for(auto k : v){
		bool flag = true;
		for(int j=0; j<k.length(); j++){
			if(s[j] != k[j]){
				flag = false;
				break;
			}
		}
				
		if(flag) chk[k.length()] = true;
	}
	
	for(int i=0; i<s.length(); i++){
		if(chk[i]){
			for(auto k : v){
				bool flag = true;
				for(int j=0; j<k.length(); j++){
					if(s[i+j] != k[j]){
						flag = false;
						break;
					}
				}
				
				if(flag) chk[i+k.length()] = true;
			}
		}
	}
	
	cout << chk[s.length()];
	return 0;
}

/*

:thinking:
이거 뭐랄까 A끼리 서로 부분문자열? 인게 문제될거같은데
그냥 길이 긴순으로 replace해서 없애면안되나

:thinking: (2)
아 음 안될거같다는거만 깨달아버림
 
*/