[백준] 돌다리 건너기

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

2602번: 돌다리 건너기

 

1. 문제이해

마법의 두루마리에 적혀있는 단어의 문자순서대로 악마의 돌다리와 천사의 돌다리를 번갈아가면서 밟을 수 있는 모든 경우의 수를 구하는 문제입니다.

2. 문제접근

접근 방식: DP

제일 못하는 재귀 DP입니다. DP[k][i][j]라고 정의했을때 k = 0인 경우는 천사의 돌다리를 건널 차례일 때 마법의 두루마리의 i번째 문자를 돌다리에서 j인덱스부터 찾는 경우를 의미합니다. 재귀를 돌면서 돌다리를 넘어다니면서 dp 배열을 채워나가면 답을 구할 수 있습니다.

3. 풀이

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

order = input().rstrip()
angel = input().rstrip()
devil = input().rstrip()

len_of_order = len(order)
len_of_bridge = len(angel)

dp = [
    [[-1] * len_of_bridge
    for _ in range(len_of_order)]
    for __ in range(2)
]

def dfs(idx, find, start):
    # 두루마리에 있는 모든 문자를 찾은 경우
    if find == len_of_order:
        return 1

    # 범위를 넘어가는 경우
    if start >= len_of_bridge:
        return 0

    # 이미 계산이 되어있는 경우
    if dp[idx][find][start] > -1:
        return dp[idx][find][start]

    total = 0

    # 천사의 돌다리를 건널 차례인 경우
    if idx == 0:
        for i in range(start, len_of_bridge):
            # 현재 찾고자하는 문자와 천사의 돌다리 문자가 같은 경우
            if order[find] == angel[i]:
                total += dfs(1, find + 1, i + 1)
    # 악마의 돌다리를 건널 차례인 경우
    else:
        for i in range(start, len_of_bridge):
            if order[find] == devil[i]:
                total += dfs(0, find + 1, i + 1)

    dp[idx][find][start] = total
    return total


print(dfs(0, 0, 0) + dfs(1, 0, 0))

4. 회고

점화식을 찾는데 꽤 애를 먹었습니다. 재귀 DP는 범위내에서의 최대, 최소값을 위해서만 사용해봤는데 이 문제는 이동하면서 dp를 계산해야하는 문제여서 신선했습니다.