[1149] RGB 거리

• 입력: 집의 개수 N, 각 집을 색칠하는 데 드는 비용. 순서대로 Red, Green, Blue
• 출력: 모든 집을 색칠하는데 드는 최소비용
• 조건: 이웃한 집은 서로 색이 같을 수 없다.
• 알고리즘: 동적계획법
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; #define min(a, b) (a < b ? a : b) #define MAX 987654321 vector<vector<int> > dp; vector<vector<int> > house; int n; int coloring(int, int); int main() { scanf("%d", &n); house = vector<vector<int> >(n, vector<int>(3)); dp = vector<vector<int> >(n, vector<int>(3, -1)); for (int i = 0; i < n; i++) scanf("%d %d %d", &house[i][0], &house[i][1], &house[i][2]); int ans = MAX; for (int i = 0; i < 3; i++) ans = min(ans, coloring(0, i)); printf("%d\n", ans); return 0; } int coloring(int here, int color) { if (here >= n) return 0; int& ret = dp[here][color]; if (ret != -1) return ret; ret = house[here][color]; int ans = MAX; for (int i = 0; i < 3; i++) if (i != color) ans = min(ans, coloring(here + 1, i)); return ret += ans; }

각 집을 색칠할 수 있는 경우는 총 3개이다. 이웃한 집이 같은 색이 아니면 되므로, 인자로 받은 color와 다른 색을 다음집에 칠해 호출한다. 이 때의 최솟값을 넘겨주고 여러 경우로 색을 칠했을 때 최솟값과 현재 집을 색칠한 값을 저장하여 반환해준다. 

• 문제 참고:https://www.acmicpc.net/problem/1149