아이디어는 어느 정도 들어맞는다고 생각했는데 가차없이 WA가 나오네요.

문제 유형대로 다이나믹 프로그래밍을 이용하였고 dp값을 다음과 같이 정의해주었습니다.

"dp[l][r][c] = 왼쪽을 기준으로 'l'번쨰 전구에서 'r'번째 전구까지 'c'의 색깔로 켜져있을 때, 모든 전구를 하나의 색깔로 만들기 위해 색을 바꿔야 하는 최소 횟수"

현재 'l'~'r'번째 전구가 'c'의 색깔이면 가능한 시도는 다음과 같습니다.

1) 왼편에 존재하는 전구와 동일한 색으로 바꾸기

ex) 전구의 색이 1 1 2 2 2 3...인 상황이고 l = 3, r = 5일떄, 1 2 2 2 2 3.... 또는 1 1 1 1 1 3... 으로 색을 바꿀 수 있음 

2) 오른편에 존재하는 전구와 동일한 색으로 바꾸기

ex) 전구의 색이 2 2 2 3 3 1...인 상황이고 l = 1, r = 3일떄, 2 2 2 2 3 1.... 또는 3 3 3 3 3 1... 으로 색을 바꿀 수 있음 

각각의 경우에 대하여 색깔을 정하는 경우의 수가 2가지씩으므로, 총 4가지의 경우를 따져봐야 합니다.

즉 식은,  dp[l][r][c] = 1+Math.min(Math.min(sol(l-1, r, C[l-1]), sol(l-1, r, c)), Math.min(sol(l, r+1, C[r+1]), sol(l, r+1, c))); 으로 표현 됩니다.

현재 전구의 색이 왼편/오른편에 있는 전구와 색이 같을 수도 있고 왼편/오른편에 전구가 없는 경우(제일 끝부분)가 생길 수도 있으므로, 그런 경우는 'sol' 함수에서 어느정도 처리를 해두었습니다.

 답을 구할 때는 N개의 전구 각각을 기준으로 색을 바꿔나가는 모든 경우를 고려해줘야 하므로 (l, r) = (1, 1), (2, 2), (3, 3), ... (N, N)인 경우 중 최소값을 골라내었습니다.

어떤 부분에서 문제가 되는 걸까요?