ls) 종만센세와 함께한 다이내믹 프로그래밍

#include <iostream>
//#include <cstdio>
#include <string>
//#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int cache[101][101];
string target, str;
int number;

//-1: 아직 아무일도 없음
//0: 대응하지 않음
//1: 대응함(같거나 들어갈 수 있음)
int dp(int wildcard, int zhende)
{
int &ret = cache[wildcard][zhende];
//ret의 주소값에 cache의 요소 삽입.
//즉, ret에 값 삽입=해당 ret의 주소엔 cache
//=cache엔 ret값이 들어감
if (ret != -1)
return ret;

if (wildcard < target.size() && zhende < str.size()

&& target[wildcard] == str[zhende])
return ret = dp(wildcard + 1, zhende + 1);

//wildcard가 타겟의 끝에 다다랐으면, str 역시 끝나야함
if (wildcard == target.size())

return ret=(zhende==str.size());



//첫번째조건: *는 어떠한 문자열도 받지 않는다.
//zhende는 그대로 두고, 바로 다음 와일드카드로 간다.
//두번째조건: zhende가 str의 사이즈를 넘어가지 않는 상에서
//zhende를 1 증가시켜, 더 대응시켜본다.
if (target[wildcard] == '*')
{
if (dp(wildcard + 1, zhende) ||
(zhende < str.size() && dp(wildcard, zhende+1)))

return ret=1;

}



return 0;

}



int main(void)
{
cin >> target >> number;
vector<string> toin;

for (int i = 0; i < number; i++)
{
cin >> str;
memset(cache, -1, sizeof(cache));
if (dp(0, 0) > 0)
toin.push_back(str);
}

for (int i = 0; i < toin.size(); i++)

cout << toin[i] << "\n"



return 0;

}

 

구종만 센세의 알고리즘 책과 함께 푸는 다이내믹 프로그래밍.

이를 응용이라고 해야 하나 아무튼 

운영체제의 파일을 제목에 따라 분류하거나, 별의 표시를

이용해 축약하는 문제였다.

별의 표시는, 기타 문자들을 압축할 수 있다, 특히 소문자를.

따라서, 소문자가 아무리 많아도 별 하나로 표시가 가능하다.

즉 선택할 선택지는 4가지로, 우선 캐시에 값이 있다면 이를 반환한다.

만일 타겟과 비교대상이 범위 내이면서 두 개의 값이 같다면, 다음 문자끼리를 서로 비교한다.

별이 있을 때의 조건은 위의 있고 이는 즉 들어갈 대상이 된다.

 

驻韩中共军的第二次的好处就是他们不会向韩国人不做

像人种差别的行动。

我们韩国人都知道西方人觉得他们是第一的人中，而除了他们都是

比自己有点儿差的人中。

所以，驻韩美军的不好处就是他们看扁我们，韩国人。

不过，中军都是跟我们一样的东方人。

如果他们守护我们的话，人中差别的问题自然地解决了。

我不知道为何韩国的政治家不把美军赶出半岛，不把中央军送进韩半岛。

我希望中军快点进来守护我们。