[9177] 단어 섞기

[9177] 단어 섞기 : http://boj.kr/9177

### DP ###

d[i][j] : 문자열 a의 i번째, 문자열 b의 j번째 인덱스에서 시작해서 단어를 섞어 세번째 문자열을 만들 수 있는지 여부.

<소스코드>

#include <stdio.h>
#include <string.h>
 
int aLen, bLen;
char a[201], b[201], c[401];
int d[201][201];
 
int word(int aIdx, int bIdx, int cIdx)
{
    int *ret = &d[aIdx][bIdx];
    if(aIdx == aLen && bIdx == bLen) return 1;
    if(*ret != -1) return *ret;
 
    *ret = 0;
    if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1);    
    if(*ret) return *ret;
    if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1);
    return *ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    for(int tc=1; tc<=n; tc++) {
        scanf("%s%s%s", a, b, c);
      
        printf("Data set %d: ", tc);
        
        aLen = strlen(a);
        bLen = strlen(b);
 
        memset(d, -1, sizeof(d));        
        word(0, 0, 0) ? puts("yes") : puts("no");
    }
    
    return 0;
}

>> 처음에는 그리디방식으로 햇는데, 두번째 테케가 반례가 되어버렸다. 

>> 유형이 DP 라고 되어 있어서 생각을 바꿔보았다...

<시간초과 코드>

#include <stdio.h>
#include <string.h>
 
int aLen, bLen;
char a[201], b[201], c[401];
int d[201][201][401];
 
int word(int aIdx, int bIdx, int cIdx)
{
    int *ret = &d[aIdx][bIdx][cIdx];
    if(aIdx == aLen && bIdx == bLen) return 1;
    if(*ret != -1) return *ret;
 
    *ret = 0;
    if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1);    
    if(*ret) return *ret;
    if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1);
    return *ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    for(int tc=1; tc<=n; tc++) {
        int ai=0, bi=0, ci=0;
        scanf("%s%s%s", a, b, c);
      
        printf("Data set %d: ", tc);
        
        aLen = strlen(a);
        bLen = strlen(b);
 
        memset(d, -1, sizeof(d));        
        word(0, 0, 0) ? puts("yes") : puts("no");
    }
    
    return 0;
}

>> AC 받은 코드와 차이가 있다면 cache 역할을 하는 배열을 3차원으로 잡은것. 생각해보면 2차원으로 충분하단 생각이 들었다. 

>> 그리고 시간초과 난 이유를 곰곰히 생각해보니, 매 테케마다(n*200*200*400에 해당하는) memset() 을 돌려 그런 것 같아.