문제풀이

다이나믹 문제로 점화식은 d[x][y][z] = 돌다리에서 x번째 y(위,아래)쪽이고 두루마리는z번째일때 경우의수이다. 위 3가지 정보를 가지고 재귀를 돌려주면 무난하게 해결할 수 있다.
첫번째 두루마리에서는 어디서든 시작할 수 있으니 위 아래 전부 호출해준다.
그 다음부터는 위쪽 아래쪽을 바꿔가며 두루마리의 문자와 맞을때 경우의 수를 추가해준다.
기저사례는 더 이상 두루마리가 없고 끝났다면 1을 return하고 돌다리가 먼저 끝난다면 두루마리를 전부 완성하지 못한경우이니 0을 return 해준다.

코드

solution

링크

boj/2602