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

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

2602번: 돌다리 건너기

---

문제

---

풀이

0. 방향성 생각

• DP
• n가지 상태 -> n+1가지 상태 존재
• dp[밟은 개수][선택한 다리][발판 번호] = 경로 개수 저장
• dp[다음 상태][선택한 다리][발판 번호] += dp[이전 상태][반대편 다리][이전 발판]
• (반대편 다리 검사, 현재 발판번호보다 작고 이전 상태에 해당하는 문자일 경우)

1. 입력

import sys
input = lambda: sys.stdin.readline().rstrip()

string = list(input())
arr = [list(input()) for _ in range(2)]
states = len(string)+1
dp = [[[0]*len(arr[0]) for _ in range(2)] for _ in range(states)]

•  

2. DP

for state,s in enumerate(string):
    for i in range(2):
        for j in range(len(arr[0])):
            if state==0:
                if arr[i][j] == s: dp[state+1][i][j] = 1
            else:
                if arr[i][j] == s:
                    ri = 1 if i == 0 else 0
                    for k in range(j):
                        if arr[ri][k] == string[state-1]:
                            dp[state+1][i][j] += dp[state][ri][k]

print(sum(sum(dp[-1][i]) for i in range(2)))

• state = 밟은 개수, i = 선택한 다리, j = 현재 발판 번호, ri = 반대편 다리, k = 현재 발판 번호 이전까지
• state = 0 인 경우, 다음 발판을 밟으면서 dp 시작점을 초기화 해준다.
• dp[1개 밟고][선택한 다리][현재 발판 번호] = 1
• state > 0인 경우 dp[다음상태][현재 선택한 다리][현재 발판 번호] += dp[이전 상태][반대편 다리][현재 발판 전까지]

 

---

전체코드

import sys
input = lambda: sys.stdin.readline().rstrip()

string = list(input())
arr = [list(input()) for _ in range(2)]
states = len(string)+1
dp = [[[0]*len(arr[0]) for _ in range(2)] for _ in range(states)]

for state,s in enumerate(string):
    for i in range(2):
        for j in range(len(arr[0])):
            if state==0:
                if arr[i][j] == s: dp[state+1][i][j] = 1
            else:
                if arr[i][j] == s:
                    ri = 1 if i == 0 else 0
                    for k in range(j):
                        if arr[ri][k] == string[state-1]:
                            dp[state+1][i][j] += dp[state][ri][k]

print(sum(sum(dp[-1][i]) for i in range(2)))

 

코멘트

입력이 작아서 그냥 현재 발판에서 뒤 순회하는 식으로 풀었는데

입력이 커지면 현재 발판까지 각 문자별 등장 횟수를 저장해서 푸는게 이상적인 방법일듯