[ 2602 ] [ DP ] 돌다리 건너기

https://www.acmicpc.net/problem/2602

2602번: 돌다리 건너기

 

풀이 과정

---

1. 경우의 수가 너무 많아질 수 있으므로 탐색으로 구하는 문제는 아닌것 같아 DP로 풀이
2. DP로 풀이하기 위해 점화식을 도출한다.
   1. DP[i][j][0] = sum(DP[v][j-1][1] , 0<= v < i)
   2. DP[i][j][1] = sum(DP[v][j-1][0] , 0<= v < i)
   3. 여기서, DP[i][j][k]에서 i가 의미하는것은 현재 위치, j가 의미하는것은 현재 문자열이 두루마리의 몇번째에 적힌 문자열인지, k가 의미하는 것은 0일땐 악마의 돌다리, 1일땐 천사의 돌다리이다.
3. 점화식을 이용하여 전체 경우의 수를 구한 전체 DP테이블에서 두루마리의 마지막 문자까지 간 경우의 수들만 더해주면 된다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
target = input()
s1 = input()
s2 = input()

dp = [[[0] * 2 for _ in range(len(target))] for _ in range(len(s1))]

for i in range(len(s1)):
    if s1[i] == target[0]:
        dp[i][0][0] = 1
    if s2[i] == target[0]:
        dp[i][0][1] = 1

for i in range(len(s1)):
    for j in range(1, len(target)):
        if s1[i] == target[j]:
            for k in range(i):
                dp[i][j][0] += dp[k][j-1][1]

        if s2[i] == target[j]:
            for k in range(i):
                dp[i][j][1] += dp[k][j-1][0]

answer = 0
for i in range(len(s1)):
    answer += (dp[i][len(target)-1][0] + dp[i][len(target)-1][1])

print(answer)