DFS

https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net dp + dfs로 문제를 해결했다. 일단 처음에는 돌의 개수 100개, 문자 개수 20개, 천사와 악마 시작으로 2개가 존재하길래 재귀를 이용한 완전 탐색으로 접근했다. 그런데 코드를 짜면서 볼때는 몰랐는데, 시간초과가 난다고 해서 급히 노선을 바꾸었다. 시간초과가 나는 이유는 나중에 알았는데 (질문), 돌 100개, 문자열 20개가 모두 같은 언어로 이루어지면 결국 2 * 100 C 20이 되기 때문이었다..