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

dp 문제를 풀다보면 어느정도 패턴이 보이는 느낌이다. 이 문제는 두루마리에 겹치는 문자가 들어올 수 있기 때문에 (RGNR 처럼 R이 두번 등장할 수 있음) 천사의 다리와 악마의 다리의 문자가 두루마리에서의 몇번째로 등장하는 해당 알파벳인지도 저장하고 있어야한다. 즉, 하나의 돌다리에 도달한 경우에 가질 수 있는 상태는 아래 3가지가 있다. 1. 왼쪽으로부터 몇번째 돌다리인지 2. 현재 밟고있는 돌다리의 글자는 두루마리의 몇번째 글자인지 3. 천사의 다리인지 악마의 다리인지 위의 세 개의 정보를 토대로 3차원 dp배열을 정의하면 아래와 같다. dp[i][j][k] :k유형(악마의 다리 or 천사의 다리)의 다리의 i번째 위치에 j번째 두루마리 글자까지 밟고 온 경우의 수 그리고 각 다리에서의 행동은 해..

2023.05.28