TennisRallies

Code

public class TennisRallies

{

    int rec(int index, int numLength, String curr, int allowed, String[] forbidden) {

        if(index == numLength) return 1;

        int ret = 0;

        for (char stroke = 'c'; stroke <= 'd'; stroke++) {

            int newAllowed = allowed;

            String newCurr = curr + stroke;

            for (int forbIndex = 0; forbIndex < forbidden.length; forbIndex++)

                if(newCurr.endsWith(forbidden[forbIndex])) newAllowed--;

            if(newAllowed <= 0) continue;

            ret += rec(index+1, numLength, newCurr, newAllowed, forbidden);

        }

        return ret;

    }

    public int howMany(int numLength, String[] forbidden, int allowed) {

        return rec(0, numLength, "", allowed, forbidden);

    }

}

Explanation

rec()함수의 newCurr에 curr 문자열 + 'c' or 'd' 를 넣고 newCurr가 금지된 문자열을 포함하는지 endsWith()로 검사한다. 금지된 문자열을 포함하면 newAllowed 값을 감소시킨다. newAllowed <= 0 이면 허용된 테니스 동작 개수를 넘어서므로 다음 문자 'd' 또는 for문을 종료한다. newAllowed > 0 이면 ret에 rec()를 재귀시켜 나온 값을 더한다. index와 numLength가 같으면 1을 반환하는 이유는 newCurr 문자열에 금지된 동작들이 포함되지 않았기 떄문이다.

References

https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm161