RGB거리 - (Dynamic programming - 동적계획법) ★★☆

 

이번 문제는 상당히 값지다고 느껴졌다.

문제를 읽고 코딩을 하기 전 어떻게 접근해야할지 끊임없이 고민했지만, dfs 같은 노가다 방법 밖에 떠오르지 않았다.

dfs로 접근을 하려 했지만 누가봐도 그렇게 한다면 시간초과가 생길 것이 뻔했고, 비효율적이였다.

 

결국 다른 사람들의 코딩을 보고 따라하는데에 그쳤지만, 한번에 이해할 수 있어서 내 것으로 만들 수 있었다.

 

접근 방법은 이러하다.

* 그림판 발퀄이라 양해부탁드립니다.

 

첫번째 집의 가격은 1, 2, 3이다.

일단 Red(1)을 칠한다고 하면 다음 번 집은 G, B밖에 못칠한다.

그 경우를 둘 다 따져보아서 (빨간선 참조) 두 집을 칠한 경우의 가격의 합을 두번 째 집에 넣는다.

 

마찬가지로 첫번째집에 초록과 파랑을 칠한 경우도 각각 구한다. (파란선, 초록선 참고)

결과적으로 두번째 집에 값은 6,7 6,8 7,8이 나오는데 최솟값을 구하는 것이므로 각각에 칸에 존재하는 최솟값만을 남긴다. (노란색 원) 

 

또다시 두번째 집을 기준으로 위의 행동을 반복한다.

 

그러면 3번째 집에서 13,14 14,15 15,15의 값이 나오고 이 중에 최솟값을 각각 구하고

마지막 집이므로 각각의 최솟값 13, 14, 15 중에 가장 작은 값인 13이 전체의 최솟값이 되게 된다.

13이 나온 화살표를 역으로 따라가 보면

 

첫번째 집에서 1 -> 두번째 집에서 5 -> 세번째 집에서 7을 선택했음을 알 수 있다.

 

이런 방식으로 해결할 수 있었던 것은 기준이 되는 집(i번째) 전 집(i-1번째)에서 골랐던 색만 제외하면 되므로

선택에 있어서 i-1번째 집만 고려해서 코딩을 하면 되기 때문이다.

 

수학적이고 이런 단순화 시킬 수 있는 생각이 코딩을 함에 있어서 정말 중요하다는 것을 깨닫게 해주는 문제였다.