[백준] 2602 돌다리 건너기

문제 링크

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

사용 알고리즘

• DP

풀이

천사 or 악마, 현재 밟고 있는 위치, 현재 문자열이 두루마리의 몇 번째 문자열인지를 저장할 DP 배열을 만들어준다.

 

우선 DP 배열을 초기화하기 위해 두루마리의 맨 처음 문자열을 밟아준다.

s, devil, angel = input(), input(), input()
dp = [[[0] * len(s) for _ in range(len(devil))] for _ in range(2)]

for now in range(len(devil)):
    if devil[now] == s[0]: dp[0][now][0] = 1
    if angel[now] == s[0]: dp[1][now][0] = 1

 

그 후, 돌다리의 각 위치마다 두루마리의 2번째 문자부터 등장하는 모든 문자에 대해서

현재 밟고 있는 위치가 두루마리에 존재한다면 `반대 돌다리에서 과거에 밟은 위치의 등장 위치 - 1`를 현재에 더해준다.

for now in range(len(devil)):
    for where in range(1, len(s)):
        if devil[now] == s[where]:
            for before in range(now):
                dp[0][now][where] += dp[1][before][where - 1]
        if angel[now] == s[where]:
            for before in range(now):
                dp[1][now][where] += dp[0][before][where - 1]

 

마지막으로 각 돌다리에 대해 i번째 위치를 밟고 있을 경우 두루마리의 마지막이 될 수 있는 경우를 더해주면 된다.

res = 0
for i in range(len(devil)):
    res += dp[0][i][-1] + dp[1][i][-1]
print(res)

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

s, devil, angel = input(), input(), input()
dp = [[[0] * len(s) for _ in range(len(devil))] for _ in range(2)]

for now in range(len(devil)):
    if devil[now] == s[0]: dp[0][now][0] = 1
    if angel[now] == s[0]: dp[1][now][0] = 1

for now in range(len(devil)):
    for where in range(1, len(s)):
        if devil[now] == s[where]:
            for before in range(now):
                dp[0][now][where] += dp[1][before][where - 1]
        if angel[now] == s[where]:
            for before in range(now):
                dp[1][now][where] += dp[0][before][where - 1]

res = 0
for i in range(len(devil)):
    res += dp[0][i][-1] + dp[1][i][-1]
print(res)