[c++] 백준 1149 RGB 거리

백준 단계별로 풀어보기 [동적계획법] RGB 거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

[풀이]

n개의 집을 빨,초,파 중 하나로 칠해야 한다. 같은 색이 연속으로 반복되면 안될 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제이다.
동적계획법으로 이 문제를 풀 때, 생각해야 할 것은 당장의 최솟값을 구해 더하는 것이 전체의 최솟값이 되지 않는다는 것이다. 예를 들어, 다음과 같이 3개의 집에 대해 빨,초,파 비용이 정해진다고 가정하자. 

빨강	초록	파랑
10	20	30
30	40	80
30	70	50

첫번째 집에서 빨간 색으로 집을 칠하는 것이 최소 가격이라고 해서 이를 선택하면, 같은 색을 연속으로 칠할 수 없으므로 두번째 집에서는 초록색 또는 파란색으로 집을 칠해야 한다. 그렇다면 10+40 또는 10+80이 되는데, 만약 첫번째 집을 초록으로 칠했다면 20+30, 20+80이 가능하고, 파랑으로 칠했다면 30+30, 30+40이 가능하다. 따라서 첫번째 집을 가장 작은 값을 가지는 빨강이 아닌 초록으로 선택해야지만 두번째 집까지의 합이 최소가 되는 것이다. 마찬가지로 세번째 집을 칠할 때는 처음 어떤 색을 칠해야 최솟값이 나올지가 확 달라질 수 있다. 따라서 처음 어떤 색으로 칠할 지 모르기 때문에 빨강, 초록, 파랑 색 별로 최솟값을 구해가야 한다. 

a번째 집을 빨강으로 칠했다고 하면, 이전의 값은 초록 또는 파랑으로 집을 칠한 2가지 경우가 있고, 이들 중 최솟값에 현재 집을 빨강으로 칠할 때 드는 비용을 더한 값을 저장한다. 초록, 파랑도 마찬가지이다. a+1번째 집을 초록으로 칠한 경우 역시 min(a번째 집을 빨강으로 칠한 최솟값, a번째 집을 파랑으로 칠한 최솟값) + a+1번째 집을 초록으로 칠한 비용으로 계산해 저장하면 된다. 

 

[코드]

#include <iostream>
#include <string>
#include <algorithm>

int main() {
	int n;
	int color[1000][3];
	std::cin >> n; //집의 수
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			std::cin >> color[i][j];
		}
	}

	int min_price[1000][3];
	min_price[0][0] = color[0][0]; //첫번째 집을 빨강으로 칠했을 때
	min_price[0][1] = color[0][1]; //첫번째 집을 초록으로 칠했을 때
	min_price[0][2] = color[0][2]; //첫번째 집을 파랑으로 칠했을 때

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			if (j == 0)
				min_price[i][j] = std::min(min_price[i - 1][1], min_price[i - 1][2]) + color[i][j];
			if (j == 1)
				min_price[i][j] = std::min(min_price[i - 1][0], min_price[i - 1][2]) + color[i][j];
			if (j == 2)
				min_price[i][j] = std::min(min_price[i - 1][0], min_price[i - 1][1]) + color[i][j];
		}
	}

	std::cout << std::min(std::min(min_price[n - 1][0], min_price[n - 1][1]), min_price[n - 1][2]);

}