1149_RGB거리

RGB거리 문제이다.

전형적인 DP문제라고 생각한다.

조건 1 RGB거리에 있는 집들은 빨강 , 초록, 파랑 색으로 칠해져야만 한다.

조건 2 이웃한 집과는 색깔이 달라야 한다.

가장 적은 돈으로 거리를 색칠 할 수 있게 할려고 할 때 그 비용은 얼마인가?

-----------------------------------------------------------------

느낌은 전체의 경우의 수를 다 구해보는 것 인데 그렇게 해도 답을 나올 것 같다. 하지만

배열을 활용한 dynamic programming방법이 더 좋을 것 같아 이 방법을 토대로 답을 구하고자 한다. 

풀이 정리

1. 우선 입력 받은 각 집들의 RGB 비용들을 arr이라는 배열에 입력 받았다. 

문제에서 

3 26 40 83 49 60 57 13 89 99

과 같이 입력 받는다.

배열은 arr[집의개수][4]; 와 같이 설정하였따. 

RGB 세가지 색깔이지만 나는 배열을 0부터 접근하는 것보다 1부터 접근하는 것을 좋아하므로 2차원 배열을 4로 선언하였다. 

1, 2, 3이렇게 접근 할 생각이다.

배열의 1차원 인덱스에는 집의 번호를 말한다. 

배열의 2차원 인덱스는 3개로 구성되는데 R , G,  B 의 비용을 입력받는다.  

arr[1][1] = 26, arr[1][2] = 40, arr[1][3] = 83

arr[2][1] = 49, arr[2][2] = 60, arr[2][3] = 57

arr[3][1] = 13, arr[3][2] = 89, arr[3][3] = 99

와 같이 입력 될 것이다. 

2. 이렇게 입력 받은 것에서 최소비용을 구해야 하는 것이 이 문제의 핵심인데

dp[집의개수][4]라는 배열을 선언하였다.

우선 dp[1][1], dp[1][2], dp[1][3]에는 arr[1][1], arr[1][2], arr[1][3]의 값들은 그대로 넣는다. 

초기 값을 선언하는 것이다. (첫 번째 집까지는 자신의 값들이 최소비용이다)

두 번째 집부터 연산을 시작하게 된다. 

2번째 집에서의 특정 RGB값 + 앞쪽까지의 RGB의 최소값에서 자신과 다른 색의 조합에서의 최소값

이라는 점화식을 세워서 풀었다. 

위의 말이 무엇이냐면

2번째 집에서 Red를 택하면 

1번째 집까지의 Green Or Blue의 색상으로 선택된 최소값과 자신(Red)을 더하여 최소값을 구하는 것이다. 

2번째 집에서 Green을 택하면

1번째 집까지의 Red Or Blue의 색상으로 선택된 최소값과 자신(Green)을 더하여 최소값을 구하는 것이다.

..........

3번째 집에서 Red를 택하면

2번째 집까지의 Green Or Blue의 색상으로 선택된 최소값과 자신(Red)를 더하여 최소값을 구하는 것이다. 

점화식을 구하자면

dp[i][j] = (j를 제외한 dp[i - 1][k] 중에서 최소값 ) + arr[i][j]가 된다.

이런식으로 dp를 수행하므로써 그때그때마다 모든 경우의 수를 세는 것보다

메모이제이션(?)을 적용하여 빠른 연산을 할 수 있으며, 사실 더 복잡하지도 않은 것 같다. 

이렇게 이차원 배열을 이용해서 dp를 수행하는 것은 처음해보는 데 기본적인 문제이지만 많은 도움이 됐던 거 같다.