프로그래머스 단어퍼즐 c++

 

처음에는 완전 탐색으로 구현할까 생각했지만, 테스트케이스를 보고 dp로 풀어야겠다고 생각했다.

 

점화식은 다음과 같다.

 

dp[i] = i번째 string까지 만들 수 있는 최소비용

 

d[i] ~ d[t.size()-1] 까지 순회를 돌면서 각각의 strs 원소가 들어가는지 확인하고, 들어가면 

 

dp[i] = min(dp[place-1]+1, dp[i])로 최소비용을 업데이트해준다.

 

그리고 첫번째 값의 경우에는 dp[place-1] 값이 존재하지 않는다. 이럴때는 1로 초기화해준다. 왜냐하면 banana 에서 b라면 최초의 경우라 1로 값이 설정되기 때문이다.

 

이렇게 dp로 풀어야한다.

 

처음에 이렇게 풀었지만, 효율성조건을 만족하지 못했다. 이는 c++ string의 시간이 오래걸리기 때문이다. 처음에는 주석처리한 부분처럼 substr을 사용해서 풀었으나 이 때 정확성 조건은 만족했지만 효율성 조건이 위배되었다. 그래서 substr이 아닌 스트링을 비교하게 for 루프를 짰다.

 

코드는 아래와 같다.

 

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

int dp[20001];

int solution(vector<string> strs, string t)
{
    int answer = 0;
    for (int i=0;i<=20001;i++){
        dp[i]=20001;
    }
    // dp[i] = i번째 자리까지를 만족시키는 최솟값
    for (int i=0;i<t.size();i++){
        for (int j=0;j<strs.size();j++){
            int place = i-strs[j].size()+1;
            if (place<0) continue;
            int flag=0;
            for (int k=0;k<strs[j].size();k++){
                if (t[place+k]!=strs[j][k]){
                    flag=1;
                }
            }
            if (flag==0){
                if (place-1<0){
                    dp[i]=1;
                }else{
                dp[i] = min(dp[i], dp[place-1]+1);
                }
            }
        }
    }
    answer = dp[t.size()-1];
    if (answer==20001){
        return -1;
    }
    return answer;
}

 

실행 결과는 아래와 같다. 점수가 표시가 된다