[DP] [BOJ 1149] RGB거리

 

1149번: RGB거리

문제

수직선 위의 N개의 집이 있을 때, 인접한 두 집의 색(R, G, B 중 하나)을 같지 않게 칠하는 최소 비용을 구하는 문제.

 

무식하게 접근하기 + 중복되는 부분 문제

모든 경우를 탐색할 때 그려지는 트리

여느 때처럼 모든 경우를 탐색해 보았을 때, 모든 전체 경우의 수는 2 * 3^N이다. N <= 1,000이니까, 말도 안되게 큰 숫자가 나와버린다. 자 그런데 그림을 보며 생각해보자. 그림에는 레벨이 4인 노드들을 R, G, B 색상에 따라서 색깔로 칠해보았다.

 

4번째에 각각의 색을 칠하는 경우는 모두 12가지가 존재한다, 그런데 이 모든 경우가 정답을 구하는 데에 있어서 필요할까? 아니다. 왜냐하면 i번째 노드의 색상을 정하는 데에는 i-1번째 집의 어떤 색상인지, 그 색상일 때의 최소 비용만 알아도 정답을 구할 수 있기 때문이다. (그 전까지 어떤 색깔을 칠했는지는 중요하지 않다.)

 

최적화를 한 후 정답을 찾아가는 과정을 그림으로 그렸다. 깊이가 늘어나도 트리의 레벨에 따른 노드의 수는 모두 같다.

 

예를 들어서 레벨이 3인 노드 중 색상이 R로 끝나는 노드는 모두 3개이다. 하지만 이를 레벨이 4인 노드에서 정답을 구할 때는 3가지 경우 중 최솟값만 알면 되므로 나머지 노드는 중요하지 않다. 즉, N번째 까지의 비용의 최솟값을 구하기 위해서는 N-1번째 집이 각각 R, G, B일 때의 최소 비용을 알고 있으면 된다. (큰 문제를 더 작은 부분 문제로 분리할 수 있다.) 이전에는 깊이가 깊어짐에 따라서 노드의 수가 2배씩 증가했지만, 최적화한 후에는 그럴 필요가 없으므로 시간복잡도는 O(N)이 된다.

 

구현