[백준-파이썬] 2602: 돌다리 건너기

문제로 가기!

헐 ㅠㅠㅠㅠ
내가 이 문제를 풀다니ㅠㅠㅠ
나는 DP 문제는 식 생각하는 게 어려워서 좀 자신이 없다... 그래서 이 문제를 봤을 때도 '내가 풀 수 있을까?'하면서 봤다.
그래도 나름 종이에 끄적끄적하다보니 이런 식으로 DP 풀면 되겠다는 생각이 났다.
그리고 하나 하나 구현했더니 맞았습니다 !! 가 나왔다 ㅠㅠㅠ 

코드를 쓰기 전에 미리 생각하는 게 중요한 것을 다시 한번 느꼈다 ! 

미리 끄적끄적한 것..ㅋㅋ

 

접근

일단 천사 다리부터 시작하는 경우, 악마 다리부터 시작하는 경우를 나눠서 생각했다.

 

악마 다리에서 시작하는 예시를 가지고 설명하겠다.

일단 dp 테이블을 다 0으로 세팅하고 시작한다. dp 테이블은 3차원 리스트로 만들었다. 무슨 다리인지, 각 다리에서 몇 번째 돌인지, 마법 두루마리에서 몇번째 글자인지를 의미한다.

그 후에 악마 다리를 쭉 본다. 마법의 두루마리에서 0번 인덱스의 글자인 R이 악마 다리의 돌에 있으면, dp 테이블에서 악마 다리의 마법 두루마리 0번 인덱스 위치에 해당하는 돌 위치를 1로 바꿔준다. 거기로 가는 방법은 1가지라는 뜻이다.

그리고 나서는 다른 다리와 번갈아가면서 본다. 방금 마법 두루마리의 첫번째 글자가 있는 다리를 밟았으니까, 이제는 두번째 글자가 있는 천사 다리의 돌을 밟아야 한다. 천사 다리를 쭉 보면서 마법 두루마리의 두번째 글자인 G가 있으면 거기로 갈 수 있는 방법을 업데이트해준다. 천사 다리의 G 돌로 갈 수 있는 방법은 악마 다리에서 R 돌이고, 지금 G가 있는 돌보다 왼쪽인 돌에서 가는 것이다. 그 개수를 세서 dp 테이블 해당 위치에 더했다.

이런 식으로 계속 다른 다리와 번갈아가면서 봤다.

코드 😍

magic_paper = input()
devil_bridge = input()
angel_bridge = input()

magic_paper_len = len(magic_paper)
bridge_len = len(devil_bridge)

ans = 0

bridge = [devil_bridge, angel_bridge]


def sol(start_bridge_type):
    global ans

    # DP 테이블
    dp_table = list(list([0] * magic_paper_len for _ in range(bridge_len)) for _ in range(2))
    # 어느 다리부터 시작하는지
    curr_bridge = start_bridge_type

    # 시작점으로 가능한 곳 체크
    for i in range(bridge_len):
        if magic_paper[0] == bridge[curr_bridge][i]:
            dp_table[curr_bridge][i][0] = 1

    # 이제 다음 다리로
    curr_bridge = (curr_bridge + 1) % 2

    # 천사-악마 다리 번갈아 가면서 가능한 수 체크
    for i in range(1, magic_paper_len):
        curr_bridge_letter = magic_paper[i]

        # 지금 찾는 다리에서 해당 문자 있는지
        for j in range(bridge_len):
            if curr_bridge_letter == bridge[curr_bridge][j]:

                # 이전 다리
                before_bridge = (curr_bridge + 1) % 2

                # 지금 다리로 올 수 있는 가능성
                for k in range(j):
                    if bridge[before_bridge][k] == magic_paper[i - 1]:
                        dp_table[curr_bridge][j][i] += dp_table[before_bridge][k][i - 1]

        curr_bridge = (curr_bridge + 1) % 2

    for i in range(bridge_len):
        ans += dp_table[0][i][magic_paper_len - 1]
        ans += dp_table[1][i][magic_paper_len - 1]


sol(0)  # 악마 다리부터 시작
sol(1)  # 천사 다리부터 시작

print(ans)