[Python] 백준 2602번: 돌다리 건너기

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

2602번: 돌다리 건너기

1. 키값을 기준으로 돌다리를 체크한다.

2. 현재 돌다리가 천사면 악마 악마면 천사로 이전 키값을 기준으로 배열을 뒤에서 부터 탐색한다.

3. 전의 키값의 dp가 저장되어있으면 모든 dp의 값을 더해주고 없으면 경로가 존재하지 않으므로 0으로 초기화한다.

(배열을 뒤에서 탐색하는이유 앞에서부터 탐색하면 경로가 0이되어 뒤에 존재하는 경로도 0이 되기때문)

4. 마지막 키값에 도달했을때 총합을 더해준다.

key = ['\0'] + list(input().strip())
eng = ['\0'] + list(input().strip())
dev = ['\0'] + list(input().strip())
dp = [[0 for _ in range(len(eng))] for _ in range(2)]
dp[0][0], dp[1][0] = 1, 1
ans = 0

def stone(a, p):
    global ans
    tmp = 0
    b = ''
    if a == dev:
        b = eng
    else:
        b = dev
    if a[j] == key[i]:
        for k in range(j-1, -1, -1):
            if b[k] == key[i-1]:
                tmp += dp[p][k]
        dp[not p][j] = tmp
        if i == len(key)-1:
            ans += tmp


for i in range(1, len(key)):
    for j in range(len(dev)-1, -1, -1):
        stone(eng, 1)
        stone(dev, 0)

print(ans)