[백준] 16500번: 문자열 판별

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

16500번: 문자열 판별

한참동안이나 붙들고 있었던 문제..ㅠㅠ

 

처음에는 정말 간단하게 아래와 같이 입력이 주어졌을 때

softwarecontest

2

software

contest

문자열 S에서 단어를 하나씩 지워가면서 문자열을 모두 지울 수 있는지를 검사하면 된다고 생각했었는데 틀린 접근법이었다.

반례는 soft, software, contest 이런식으로 단어가 주어지는 경우(한 단어가 다른 단어의 sub string인 경우)를 생각해보면 된다.

 

그래서 어떻게 풀지 한참을 고민하다가 결국 다른분들이 푼 것을 참고했다.

---

결론! 이 문제도 동적 계획법으로 풀면 된다.

그렇다면 무엇을 메모이제이션 할것인가?

 

dp[pos]는 문자열의 pos번째 글자부터 마지막 글자까지의 sub string을 주어진 단어를 만들 수 있는지를 나타낸다(만들 수 있으면 1, 없으면 0)

따라서 dp[101] 배열을 선언해야 한다. (101 = 문자열의 최대 크기(100) + 1)

한 칸을 더 만들어주는 이유는 구현을 편하게 하기 위해서이다.

 

예시의 경우, dp 배열은 아래와 같이 만들어진다.

s	o	f	t	w	a	r	e	c	o	n	t	e	s	t
1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1

dp 배열을 만들기 위해, 문자열 S를 마지막 글자부터 탐색하면서

i) 해당 위치(pos)에 일치하는 단어가 있고,

ii) dp[pos + 단어의 길이] = 1이면

dp[pos]에 1을 입력해준다.

 

최종적으로 dp[0]에는 전체 문자열을 주어진 단어로 만들 수 있는지 여부가 담겨있으므로, dp[0]을 출력해주면 끝

#include <iostream>
#include <string>
using namespace std;

int main(void) {
	string S;
	int N;
	string A[100];
	int dp[101];

	cin >> S;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	dp[S.length()] = 1;

	for (int pos = S.length() - 1; pos >= 0; pos--) {
		for (int j = 0; j <= N; j++) {
			if (S.find(A[j], pos) == pos && dp[pos + A[j].length()] == 1) {
				dp[pos] = 1;
				break;
			}
			else {
				dp[pos] = 0;
			}
		}
	}

	cout << dp[0];
}

어려워..ㅠㅠ