팁스타운 배 코드챌린지 본선 - 3번

예전에 풀었던 백준넷 단어와 주기율표 문제의 다운그레이드 버전

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

저 문제는 조건이 상당히 까다로워 아직도 푼 사람이 두명밖에 없어서 뿌듯하다 ㅋㅋㅋ

동적 계획법 문제인데, dp(state)를 state~끝 문장을 처리 할 때 필요한 최소 단어 조각 갯수로 정의했다

최대 단어 조각 길이는 5이므로 state부터 한자리씩 추가해가면서 단어 조각 목록에 있는지를 검사해 있으면 그 다음 글자부터 필요한 단어 조각 갯수를 계산하는 과정을 다섯번 반복한다. 그 중 최소값을 반환하면 된다.

int d[20001];

set<string> dictionary;

string str;

int dp( int state)

{

if(state>=str.length()) return 0;

int &ret  = d[state];

if(ret != -1) return ret;

int res = 987654321;

string match = "";

for(int i=state; i<state+5; i++)

{

match+=str[i];

if(dictionary.find(match) != dictionary.end())

{

res = min(res, dp(i+1)+1);

}

}

return ret = res;

}

int solution(vector<string> strs, string t)

{

int answer = 0;

dictionary.clear();

memset(d,-1,sizeof(d));

str = t;

for(auto i=strs.begin(); i!=strs.end(); i++)

dictionary.insert(*i);

int ret = dp(0);

if(ret > 20001) return -1;

return ret;

}