[백준] 1563번 - 개근상 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상

-> https://www.acmicpc.net/problem/1563

1563번: 개근상

 

cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된 개수만 세어주면된다.

 

 

 

C++ 소스코드)

 

 

PS. Top-down으로 풀려다 시간 지체됐다...