집을 R, G 또는 B로 칠하는 경우 인접한 집(+첫 집과 끝 집)끼리는 같은 색을 칠할 수 없을 때, 집을 칠하는 데에 필요한 최소 비용을 구하는 문제입니다. ① 1149 - RGB거리 문제와 조건이 거의 비슷한데, 한 가지 다른 점은 첫 집과 끝 집도 색이 달라야 한다는 점입니다. 1149번 문제는 이전 집에 무엇을 색칠했는지에 따라 DP 배열의 다른 위치에 최소 비용을 저장해가면서 답을 구했는데, 이번에는 첫 집의 색이 무엇인지도 같이 저장을 해야겠습니다. 그러면 한 집을 탐색하는 도중에 구해야 할 DP 값이 9개가 됩니다. 이전 집이 무슨 색인지(3개)와 첫 집이 무슨 색인지(3개)를 모두 고려해야하기 때문이죠. 아래와 같은 규칙으로 DP값을 업데이트하면 답을 구할 수 있을 것입니다.
0 : R / 1 : G / 2 : B
dp[i][j] : 현재 집에 i색을 칠하고 첫 집에 j색을 칠하는 경우 최소 비용
dp[0][0] = cost[0][0];
dp[1][1] = cost[0][1];
dp[2][2] = cost[0][2];
new_dp[0][j] = min(dp[1][j], dp[2][j]) + cost[i][0];
new_dp[1][j] = min(dp[0][j], dp[2][j]) + cost[i][1];
new_dp[2][j] = min(dp[0][j], dp[1][j]) + cost[i][2];
PS알못 OrbitHv의 PS