[2602] 돌다리 건너기

[2602] 돌다리 건너기 : http://boj.kr/2602

- 난 3차원으로 풀었는데, 다른 사람들은 2차원으로 풀었다. 

d[bidx][ad][sidx] : 상태가 ad(0은 천사차례, 1은 악마차례) 일때, 

       bidx번째 돌다리에서, sidx 번째 문자부터 시작하는 문자열에 적힌 순서대로 다리를 건널 수 있는 방법의 수

<소스코드>

#include <stdio.h>
 
char str[21];
char ang[101], dev[101];
int d[101][2][21];
 
int bridge(int bidx, int ad, int sidx)
{
    int *ret = &d[bidx][ad][sidx];
    if(!str[sidx]) return 1;
    if(ad == 0 && !ang[bidx]) return 0;
    if(ad == 1 && !dev[bidx]) return 0;
    
    if(*ret) return *ret;
 
    if(ad == 0) {
        if(ang[bidx] == str[sidx])
            *ret = bridge(bidx+1, !ad, sidx+1);
        *ret += bridge(bidx+1, ad, sidx);
    }
    else {
        if(dev[bidx] == str[sidx])
            *ret = bridge(bidx+1, !ad, sidx+1);
        *ret += bridge(bidx+1, ad, sidx);
    }
    return *ret;
}
 
int main()
{   
    scanf("%s%s%s", str, ang, dev);
    printf("%d\n", bridge(0, 0, 0)+bridge(0, 1, 0));
    return 0;
}

>> 천사다리를 먼저 택한 경우 + 악마다리를 먼저 택한 경우