[1일 1알고] 단어 퍼즐

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

프로그래머스

 

글을 읽자마자 깊은 dp의 향기가 느껴집니다.

스읍ㅈ

 

strs의 크기도 작고 t의 크기도 작고 단어 조각의 크기도 작기 때문에 

어떻게 풀어도 잘못푼것만 아니면 좋게좋게 넘어가줄 것 같네요

---

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

bool check(string& src, string& comp, int N, int idx, int size)
{
    if (idx + size > N)
        return false;
    for (int i = idx; i < idx + size; ++i)
    {
        if (src[i] != comp[i - idx])
            return false;
    }
    return true;
}

int solution(vector<string> strs, string t)
{
    int answer = 0;

    int N = t.size();
    vector<pair<char, int>> dp(N+1);
    dp[0] = { ' ', 0 };
    for (int i = 1; i <= N; ++i)
    {
        dp[i] = { t[i-1], 20001 };
    }

    for (int i = 1; i <= N; ++i)
    {
        int M = strs.size();
        for (int j = 0; j < M; ++j)
        {
            int size = strs[j].size();
            if (check(t, strs[j], N, i - 1, size))
            {
                dp[i + size - 1].second = min(dp[i + size - 1].second,
                    dp[i - 1].second + 1);
            }
        }
    }

    if (dp[N].second == 20001)
        answer = -1;
    else
    {
        answer = dp[N].second;
    }
    return answer;
}

처음에는dp의 초기갓을 INT_MAX로 잡았는데 생각해보니 비교할 때 +1을 하면 overflow가 발생하더라고요 

 

이런 사소한 점을 주의해야하겠습니다.