문제

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

문제풀이

사용한 알고리즘 : DP

a~z 26개의 단어 중 어떤 것으로 끝나는지 구분하여 저장합니다.

'S[x] : 'x로 끝나는 단어' 라고 설정한 벡터를 하나 만들었습니다.

'dp[k] : k~끝까지 만들 수 있는지 여부'라고 설정한 dp를 bool 형식으로 만들어줍니다.

우리 목표는 문자열 S 의 뒤에서부터 주어진 목록 A의 단어들을 채워 나가는 것입니다.

문자열 S의 첫번째 단어까지 채워지면 1을 출력할 것이고, 아니면 0을 출력할것입니다.

문자열 S의 맨 뒤 글자부터 탐색을 할 것입니다.

i번째를 탐색할 시, i+1 까지 채워졌다면 i번째에 들어갈 수 있는 단어를 넣어볼 것입니다.

따라서 문자열 S 길이 바로 뒷 글자는 채워졌다고 생각하고 탐색을 시작합니다.

i번째 탐색시, S의 i번째와 같은 글자로 끝나는 단어들을 봅니다.

각 단어가 들어갈 수 있는지 확인하고,

들어갈 수 있다면 단어가 들어간 길이만큼 앞의 dp값을 최신화 해줍니다.

dp[0]=true 이면 0에서~끝까지 채워질 수 있다는 것입니다.

이를 생각하여 답을 출력해줍니다.

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

	string S;
	int N;
	vector<string> arr[26]; // S[t] : 글자 t 로 끝나는 단어들
	bool dp[111]; // dp[x] : x ~ 끝까지 채울 수 있는지 여부

	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> S;
	cin >> N;
	for (int i = 0; i < N; ++i) { // N 개의 단어들
	string ss;
	cin >> ss;
	int x = ss.back() - 'a'; // 끝 글자
	arr[x].push_back(ss); // 해당 단어로 끝난다고 생각해서 저장
	}

	dp[S.length()] = true; // 바로 뒷 글자는 채워졌다고 생각
	for (int i = S.length() - 1; i >= 0; i--) {
	if (!dp[i + 1]) continue; // 이전까지 채워졌는지 여부 확인

	int now = S[i] - 'a'; // S 의 현재 보고 있는 글자

	for (auto it : arr[now]) {// S[i] 와 같은 단어로 끝나는 애들만 탐색
	int L = it.length(); // 들어갈 단어길이
	int To = i - L + 1; // i 부터 L 길이의 단어를 앞으로 붙일 수 있는지
	if (To < 0) continue; // 단어길이가 넘어가면 pass

	bool ok = true;
	for (int j = 0; j < L; ++j) {
	if (S[i - j] != it[(L - 1) - j]) {
	ok = false;
	break;
	}
	}
	if (ok) dp[To] = true; // dp값 최
	}
	}

	if (dp[0]) cout << 1 << '\n';
	else cout << 0 << '\n';

	return 0;
	}

view raw BOJ 16500.cpp hosted with ❤ by GitHub