문제: RGB 거리 2

문제풀이 접근법

문제에서 우리가 구해야 하는 것은 아래 조건에 따라서 집의 색을 칠할 때의 최소 비용입니다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

만약 이 문제가 첫번쨰, 두 번째 조건이 없이 단순히 '인접하는 집끼리의 색이 같지 않아야 한다'의 조건이었다면, 인덱스를 1부터 증가시켜가면서 이전에 선택할 수 있었던 최적을 선택을 하는 DP문제로 풀이를 진행했을 것입니다.

하지만 끝에 위치한 집들끼리도 서로 색이 같지 않아야 한다는 위 조건들 때문에, 이 문제에서는 세 번의 DP 테이블 작성으로 문제를 해결했습니다. 첫 집의 색깔을 고정을 시켰을 때의 최소값들을 모두 고려해야 했기에. 결국 주어진 색깔의 개수 * 집의 개수만큼의 순회를 진행한 셈이죠.

그렇다면 어떻게 처음에 선택하는 집의 색(i=1)을 '고정'할 수 있을까요? 바로 고정하고자 하는 집의 색이 아닌 색의 비용을 임의로 크게 조작을 해주면됩니다. 그렇게 된다면 두 번째의 집의 색(i=2)을 선택하고자 할 때, 고정하고자 하는 집의 색이 비용이 가장 적어 고정하고자 하는 집의 색을 선택할 수밖에 없게 됩니다.

현재 비용의 최대값은 1000이기에, 고정되지 않은 나머지 색에 대한 비용은 1001로 설정해 주었습니다.
첫 번째 집의 색을 각 색상마다 고정하는 것은 다음과 같겠네요.

이후에는 RGB 거리 문제와 동일합니다. 현재 i 번째 집을 a 색으로 칠하는 것이 가능하다면, a색이 아닌 색을 칠한 i-1번째의 시행이 선행되어야겠죠. 가령 i 번째 집을 빨강으로 칠하려고 한다면, i-1번째 집은 초록, 또는 파랑으로 칠해져야 할 것입니다.

그럼 이 조합을 다 구해야하는가? 아닙니다. DP 테이블을 이용하는 장점이 바로 여기서 드러납니다.

만약 DP테이블을 이용하여 누적된 비용을 저장한다면, i-1번째 집이 초록이기 위해서 어떤 선택을 했어야 했는지를 역추적할 필요가 없이, 단순히 DP 테이블의 i-1 번째 값만 바라보면 됩니다.

다시 본론으로 돌아가서 i 번째 집을 빨강으로 칠하려고 하는 경우, 우리는 dp 테이블의 i-1번째 행의 초록과 파랑에 해당하는 열을 바라보면 됩니다. dp테이블의 i-1번째 행의 초록에 해당하는 열은 어찌저찌해서 i-1번째 집을 초록색으로 칠했을 때 누적 비용의 값을 담고 있겠죠. 파랑에 해당하는 열도 마찬가지이구요.

이를 점화식으로 표현하자면,

//배열 costs는 입력값으로 주어진 집들의 색깔 별 비용이 담긴 배열
 dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]
 dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]
 dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]

가 되겠습니다.

그렇게 첫 집의 색을 빨강, 초록, 파랑으로 고정시킨 후, DP 테이블을 채우면 각 순회마다 DP 테이블의 N 번째 행에는 첫 집의 색을 고정하였을 때 모든 집을 칠하는 비용이 담기게 됩니다.

이 3개의 값 중 하나는 반드시 첫 집의 색과 같은 색으로 N번째 집을 칠한 케이스가 존재합니다. 문제에서는 이 경우를 배제하라고 하였기에, 이 경우를 제외시켜줍니다.

구현 시 어려웠던 점과 깨달음

• 저는 색을 '고정'해야하는 것을 알았지만, 어떻게 구현해야할 지 막막했습니다.
• '고정된 색'은 다음 선택에서는 '가장 최적의 선택이 된다는 것'이며, 1번째 특정 색을 제외한 나머지 색의 값을 임의로 크게 조작해주면 2 번째 선택에서는 반드시 1번째에서 고정한 색을 선택할 수밖에 없게 됩니다.

이 문제가 어려웠다면....

비슷한 유형의 문제인 RGB 거리 문제를 먼저 푸는 것을 추천드립니다!

RGB거리 문제와 이 문제의 차이점을 생각하면서 접근한다면 조금 더 얻어가는 것이 많을 것이라 생각됩니다.

우리가 예전에 원형 테이블에 의자를 놓는 경우의 수를 구하려구 할 때, 첫 번째 의자의 위치를 고정시켜놓고 계산을 진행했던 것이 기억이 납니다. 이 문제도 원형 문제라고 생각이 들었구요. 참으로 재밌고, 의미있는 문제였습니다.