[BOJ] 백준 1149번: RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

동적 계획법을 사용하는 문제입니다.

i번째 집을 j번째 색으로 칠할 때의 비용 color[i][j]에 대하여

i번째 집까지 색을 칠할때 i번째 집을 j번째 색으로 칠하는 최소비용을 dp[i][j]라고 한다면

이웃한 집은 같은색으로 칠하면 안되므로 

dp[i][j] = min(dp[i][j], dp[i-1][k] + color[i][j]) 단, k ≠ j 이 됩니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef long long ll;


int n;
int dp[1001][3] = { 0, };
int color[1001][3];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> color[i][j];
		}
	}
	for(int i = 0; i < 3; i ++)
		dp[0][i] = color[0][i];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			dp[i][j] = 2e9;
			for (int k = 0; k < 3; k++) {
				if (k != j) {
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + color[i][j]);
				}
			}
		}
	}
	cout << min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));
}