[프로그래머스][level4] 단어 퍼즐 (C++)

https://programmers.co.kr/learn/courses/30/lessons/12983

코딩테스트 연습 - 단어 퍼즐

 

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 문제를 해결할 수 있습니다.

dp 배열을 선언하여 아래와 같이 정의합니다.
dp[i] = 문자열 t의 i번째 문자부터 시작하는 문자열을 만들 때 필요한 단어 조각의 최솟값.

Top-down DP를 이용하였습니다.

dp[n]을 구하고 리턴하는 sol(n)은 아래와 같은 과정을 통해 구해집니다.

for(auto& s : str){
    if(check(n,s)) ret=min(sol(n+s.size()),ret);
}
return ++ret;

str의 모든 단어 조각 s들을 확인하면서 t의 n번 index부터 시작하는 부분 문자열을 대체할 수 있는지를 체크합니다.
대체할 수 있다면 sol(n)=1+sol(n+s.size()) 으로 업데이트 할 수 있습니다. 하지만 이 값이 최솟값인지는 알 수 없기 때문에
모든 s들을 확인하면서 min값으로 업데이트 해줍니다. 위의 코드에서는 +1은 return 시에 해주었습니다.

 

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<string> str;
string t;
int dp[20001],inf=9e7;;
bool check(int n,string& s){
    for(int i=0;i<s.size();i++){
        if(n+i>=t.size()) return 0;
        if(t[n+i]!=s[i]) return 0;
    }
    return 1;
}
int sol(int n){
    if(n==t.size()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=inf;
    for(auto& s : str){
        if(check(n,s)) ret=min(sol(n+s.size()),ret);
    }
    return ++ret;
}
int solution(vector<string> _strs, string _t){   
    memset(dp,-1,sizeof(dp));
    str=_strs;
    t=_t;
    return sol(0) >= inf ? -1 : sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/단어_퍼즐.cpp