돌대가리

[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 돌대가리 건너기 다이나믹 프로그래밍 처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다.. 결국 어쩔 수 없이 구글을 참고했는데.. 단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다 dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수] 처음 dp배열을 -1로 초기화 시켜주고 현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의..