SLENDER ANKLES's 개발블로그

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를 수행하는 것은 처음해보는 데 기본적인 문제이지만 많은 도움이 됐던 거 같다. 

1차원적으로 생각했다. 

돌게임에서 수근이 또는 창영이는 자신의 턴마다 1개 또는 3개를 가져 갈 수 있다고 했다. 

결국 어떠한 형태로 가져가든 간에 1개씩 가져가든 3개씩 가져가든, 홀수개만큼을 가져가는 것이기 때문에 누구의 턴에서 끝나는지는 사실 정해져 있다는 것을 깨달았다. 

나의 풀이 방법은 

(전체 돌의 개수 /  3) + (전체돌의개수 % 3)

와 같다. 이렇게 게임이 최종 몇 번안에 완료가 되는지를 구하고

그 완료된 게임의 횟수가 짝수이면 창영이가 승! 홀수이면 수근이가 승!이라고 판정했다.

// 풀고나서 생각해보았는데

어차피 전체 돌을 한 개씩 가져가면서 시행되는 게임의 횟수를 짝수인지 홀수인지 계산하면되므로 

전체돌의 개수 % 2 == 0  이면 창영 승

전체돌의 개수 % 2 == 1  이면 수근 승 

이렇게 판정하면 된다. 

우선 배열의 인덱스와 다른 형태의 입력 값을 받는 것을 고려해야 된다. 

방향만 바꾸어서 생각하면 된다.

문제는 달팽이 모양처럼 배열을 타고 들어가야 되는데 재귀적으로 풀어냈다. 

기본 포맷은 DFS에 착안했다. 물론 DFS는 아니다. 

기본 아이디어는 재귀적 함수 호출에 DIRECTION정보를 넘겨주며 DIRECTION방향으로 더이상 진행 할 수 없을 때 DIRECTION방향을 바꾸어주는 방법으로 문제를 해결해나갔다. 

어떤 의미인지 잘 이해가 안 갈 수도 있겠다. 

(1,1)에서 시작했을 때 

무조건 방향은 오른쪽방향 -> 아래방향 -> 왼쪽방향 -> 위쪽방향 으로 흐르게 되어있다.

그래서 방향을 int 형으로 만들어 생각했다.

right : 1, down : 2, left : 3, up : 4

그래서 현재 방향점에서 진행 가능하면 기존방향으로의 좌표를 증가시켜주면서 현재까지의 현재까지 진행된 순번번호를 함수의 인자로 넘겨서 답을 구하는 방식이다. 

다시 한 번 정리해서 올려야 겠다!