[백준] 2602 돌다리 건너기 (골드 4)

dp 문제를 풀다보면 어느정도 패턴이 보이는 느낌이다.

 

 

이 문제는 두루마리에 겹치는 문자가 들어올 수 있기 때문에 (RGNR 처럼 R이 두번 등장할 수 있음)

 

천사의 다리와 악마의 다리의 문자가 두루마리에서의 몇번째로 등장하는 해당 알파벳인지도 저장하고 있어야한다.

 

즉, 하나의 돌다리에 도달한 경우에 가질 수 있는 상태는 아래 3가지가 있다.

1. 왼쪽으로부터 몇번째 돌다리인지

2. 현재 밟고있는 돌다리의 글자는 두루마리의 몇번째 글자인지

3. 천사의 다리인지 악마의 다리인지

 

 

위의 세 개의 정보를 토대로 3차원 dp배열을 정의하면 아래와 같다.

 

 

dp[i][j][k] :k유형(악마의 다리 or 천사의 다리)의 다리의 i번째 위치에 j번째 두루마리 글자까지 밟고 온 경우의 수

 

 

그리고 각 다리에서의 행동은 해당 알파벳이 두루마리의 첫번째 문자열인지 아닌지에 따라서 달라진다.

 

1. 두루마리의 첫번째 문자열이라면 해당 dp값을 1로 설정해주고 현재 다리와 다른 종류의 다리를 확인하며 다음 알파벳이 있는지 확인한다.

 

2. 첫번째 문자열이 아니라면 현재 다리와 다른 종류의 다리를 확인하며 다음 알파벳이 있는지 확인한다.

 

 

다른 종류의 다리를 확인하는 과정에서는 두루마리에 등장하지 않는 알파벳이 존재하는 경우 밟지 않으므로 다음 돌다리로 넘어가서 체크한다.

 

 

정답 코드는 아래와 같다.

 

 

## 11 05 

import sys
input = sys.stdin.readline

durumari = input().rstrip()
devilString = input().rstrip()
angelString = input().rstrip()


durumariDict = {}
for index, item in enumerate(durumari):

    if item not in durumariDict:
        durumariDict[item] = {index}

    else:
        durumariDict[item].add(index)

durumariSet = set(durumari)


## dp[i][j][k] : k유형의 다리의 i번째 위치에 j번째 두루마리 글자까지 밟고 온 경우의 수
dp = [[[0 for _ in range(2)] for _ in range(len(durumari))] for _ in range(len(devilString))]


## 결과값을 저장한다.
result = 0


## 다리를 하나씩 확인한다.
for i in range(len(devilString)):

    devilChar = devilString[i]
    angelChar = angelString[i]

    ## 악마다리 한번, 천사다리 한번 순회하기
    for j in range(2):
        
        ## 악마 다리를 순회하는 과정
        if j == 0:

            ## 두루마리에 없는 문자라면 건너뛰기
            if devilChar not in durumariSet:
                continue


            for durumariIndex in durumariDict[devilChar]:
                
                ## 두루마리의 첫번째 글자인 경우
                if durumariIndex == 0:
                    
                    dp[i][durumariIndex][j] = 1

                    
                    ## 두루마리 인덱스가 마지막 인덱스라면 result 업데이트 해주기
                    if durumariIndex == len(durumari) - 1:
                        result += dp[i][durumariIndex][j]
                        continue



                    for nextIndex in range(i+1, len(devilString)):
                        
                        ## 천사다리의 nextIndex번째의 문자가 다음으로 밟아야 할 문자와 같다면
                        if angelString[nextIndex] == durumari[durumariIndex+1]:
                            
                            ## 천사다리의 해당 위치에 현재 위치의 값 더해주기
                            dp[nextIndex][durumariIndex+1][j^1] += dp[i][durumariIndex][j]

                
                ## 두루마리의 첫번째 글자는 아닌 경우
                else:
                    
                    ## 첫번째 글자가 아닌 데 도달하지 못했다면 다음으로 가기
                    if dp[i][durumariIndex][j] == 0:
                        continue

                    
                    ## 두루마리 인덱스가 마지막 인덱스라면 result 업데이트 해주기
                    if durumariIndex == len(durumari) - 1:
                        result += dp[i][durumariIndex][j]
                        continue



                    for nextIndex in range(i+1, len(devilString)):
                        
                        ## 천사다리의 nextIndex번째의 문자가 다음으로 밟아야 할 문자와 같다면
                        if angelString[nextIndex] == durumari[durumariIndex+1]:
                            
                            ## 천사다리의 해당 위치에 현재 위치의 값 더해주기
                            dp[nextIndex][durumariIndex+1][j^1] += dp[i][durumariIndex][j]

        ## 천사 다리를 순회하는 과정
        else:

            ## 두루마리에 없는 문자라면 건너뛰기
            if angelChar not in durumariSet:
                continue

            for durumariIndex in durumariDict[angelChar]:
                
                ## 두루마리의 첫번째 글자인 경우
                if durumariIndex == 0:
                    
                    dp[i][durumariIndex][j] = 1

                    
                    ## 두루마리 인덱스가 마지막 인덱스라면 result 업데이트 해주기
                    if durumariIndex == len(durumari) - 1:
                        result += dp[i][durumariIndex][j]
                        continue



                    for nextIndex in range(i+1, len(angelString)):
                        
                        ## 악마다리의 nextIndex번째의 문자가 다음으로 밟아야 할 문자와 같다면
                        if devilString[nextIndex] == durumari[durumariIndex+1]:
                            
                            ## 천사다리의 해당 위치에 현재 위치의 값 더해주기
                            dp[nextIndex][durumariIndex+1][j^1] += dp[i][durumariIndex][j]

                
                ## 두루마리의 첫번째 글자는 아닌 경우
                else:
                    
                    ## 첫번째 글자가 아닌 데 도달하지 못했다면 다음으로 가기
                    if dp[i][durumariIndex][j] == 0:
                        continue

                    
                    ## 두루마리 인덱스가 마지막 인덱스라면 result 업데이트 해주기
                    if durumariIndex == len(durumari) - 1:
                        result += dp[i][durumariIndex][j]
                        continue



                    for nextIndex in range(i+1, len(devilString)):
                        
                        ## 악마다리의 nextIndex번째의 문자가 다음으로 밟아야 할 문자와 같다
                        if devilString[nextIndex] == durumari[durumariIndex+1]:
                            
                            ## 천사다리의 해당 위치에 현재 위치의 값 더해주기
                            dp[nextIndex][durumariIndex+1][j^1] += dp[i][durumariIndex][j]


print(result)