BOJ 2602 - 돌다리 건너기

문제 링크

---

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

문제 해결

---

1. " 한 방향으로 이동 + 모든 경우의 수 " 에서 Dynamic Programming으로 해결

2. dp[i][j][k] = i (천사 또는 악마) 행, j (돌다리) 열을 밟았을 때 두루마리 속 k번째 문자를 밟은 경우의 수.

3. Top-down 형태로 풀려고 애썼다.

주의할 점 || 생각해볼 점

---

1. Dp 배열을 만드는 것이 어려웠다. 완전 탐색 하면서 놓치지 않아야 할 정보를 담아야한다.

2. 기저 조건을 설정하는 것이 익숙하지가 않았다. 가령 최대 인덱스가 k라면, k+1에서 기저 조건을 수행.

※ 정확하고 부드러운 태클은 언제나 환영입니다.