프로그래머스 알고리즘 문제 단어퍼즐

단어퍼즐 (프로그래머스 알고리즘)

https://school.programmers.co.kr/learn/courses/30/lessons/1882

처음에는 문자열을 통한 ‘탐색’인 줄 알고
백트래킹을 포함한 DFS로
unordered_map을 이용한 풀이를 사용하였다
그러나, 효율성 문제를 통과하지 못하였고
개선을 하려 최대한 노력하였는데, 답이 보이지 않아 확인해보니
DP를 사용하는 방식으로 풀 수 있었다

dp를 통하여
‘dp[i] : 주어진 t의 i를 만드는데 필요한 최소 횟수’
를 정의하고 문제를 푸는 방식이다

1. i를 점차 증가시키고, 이후 1~5 사이즈의 ‘단어’가 해당 ‘왼쪽 문자열’에 포함되는지를 체크
   
2. 단어가 존재하는 경우, dp[i] 가 dp[i-j] + 1 보다 크다면 갱신해준다
   
3. 문자열 size까지 반복
   

풀이 자체를 이해하기 어려운 것은 아니였지만
개인적으로는 문제에 DP의 적용 개념의 ‘시도’가 참 어려운 듯 하다

Code

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int solution(vector<string> strs, string t) {
	unordered_set<string> dict(strs.begin(), strs.end());

	const int tSize = t.size();

	// dp[i]는 t의 첫 i글자를 만드는데 필요한 최소 횟수
	vector<int> dp(tSize + 1, tSize + 1);

	dp[0] = 0; // 빈 문자열을 만드는 데 필요한 횟수는 0

	for (int i = 1; i <= tSize; ++i)
	{
		// strs의 모든 문자열 길이는 최대 5이므로
		for (int j = 1; j <= 5; ++j)
		{
			// i-j부터 추출하기
			// 현재의 i 부터
			// j로 좌측으로 당기면서 부분 문자열을 추출하고
			// 그것을 비교하는 방식이다
			if (i - j >= 0)
			{
				// i~j의 위치부터, j의 길이까지 추출하기
				// t의 부분들을 '잘라'
				// 해당 단어 부분이 'strs' 로 만든 set에 있는지 확인한다
				string part = t.substr(i - j, j);
				if (dict.find(part) != dict.end())
				{
					// 단어가 있다면 dp[i]에 기존 것과
					// dp[i-j] + 1과 비교
					dp[i] = min(dp[i], dp[i - j] + 1);
				}
			}
		}
	}

	int answer = -1;
	if (dp[tSize] != tSize + 1)
		answer = dp[tSize];

	return answer;
}