코딩스토리

www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net KOALA의 이번 주 모의테스트 문제였다. 누가 봐도 DP 문제였다. 처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ 핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다. dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다. 나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다. 마법의 두루마리에 적힌 ..