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

1.문제설명

처음 봤을 때 이게 왜 다이나믹 프로그래밍 문제일까 의문이 드는 문제입니다.

어떻게 다이나믹 프로그래밍으로 구현해야할지 고민이 필요합니다.

다이나믹 프로그래밍의 핵심은

주어진 문제를 여러개의 부분 문제로 나누어 풀고

그 결과를 이용해서 주어진 문제를 해결 하는 것입니다.

주어진 S 문자열의 0번 char부터 A 집합의 문자열들과 서로 비교하면서

A의 문자열이 S문자열의 부분과 일치하는지 확인합니다.

이 과정을 반복해서 S문자열의 몇번째 char 까지 만들 수 있는지

bool자료형의 dp 배열에 저장해두면서 그 이후의 부분을 만들 수 있는지 판단하면 됩니다.

그림을 보면 이해하기 쉬울겁니다.

softwarecontest와 software이 7번째 까지 일치하니까

dp[8] = true로 만들어줍니다

7이 아니라 8에 두는 건 인덱스 관리가 7에두는 것보다 다음 숫자인 8에 두는게 쉽기 때문입니다.

그 후 dp배열을 확인하면서 dp[i] == 1 인 지점부터 다시 A의 문자열들과 비교해줍니다

software은 다르니까 넘어가게 되고 contest가 8번부터 일치하므로 다시 dp[15] == 1로 만들어줍니다.

결과상 dp[S.length()] == 1 이라면 문자열 S를 만들 수 있다는 뜻입니다.

2.문제풀이코드 C++

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

int n;
bool dp[101];
string s;
vector<string> A;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		A.push_back(tmp);
	}

	for (int i = 0; i < s.length(); i++) {
		if (dp[i] || i==0) {
			int st = i;
			
			for (int j = 0; j < n; j++) {
				//부분문자열을 합칠 때 원래 문자열보다 더 길어지는 경우는 제외
				if (st + A[j].length() > s.length()) continue;

				bool flag = true;
				for (int k = 0; k < A[j].length(); k++) {
					if (A[j][k] != s[st + k]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					dp[st + A[j].length()] = 1;
				}
			}
		}
	}

	cout << dp[s.length()];


	return 0;
}