RGB 거리 - 백준 1149

나같은 바보도 없다.

백트래킹 Solution  시간초과 및 메모리 초과

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
#include <map>

using namespace std;
int n = 1;
int mina = 210000000;
int arrayRGB[1001][3];
void rec(string s, int v) {
	if (v > mina) {
	}
	else {
		cnt++;
		if (s.size() == n) {
			mina = v;
			
		}
		else {
			string tmp1 = s;
			string tmp2 = s;

			if (s.back() == 'R') {
				rec(tmp1.append("G"), v + arrayRGB[s.size()][1]);
				rec(tmp2.append("B"), v + arrayRGB[s.size()][2]);
			}
			else if (s.back() == 'G') {
				rec(tmp1.append("R"), v + arrayRGB[s.size()][0]);
				rec(tmp2.append("B"), v + arrayRGB[s.size()][2]);
			}
			else {
				rec(tmp1.append("R"), v + arrayRGB[s.size()][0]);
				rec(tmp2.append("G"), v + arrayRGB[s.size()][1]);
			}
		}
	}
	
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int r, g, b;
		cin >> r >> g >> b;
		arrayRGB[i][0] = r;
		arrayRGB[i][1] = g;
		arrayRGB[i][2] = b;

	}
	rec("R", arrayRGB[0][0]);
	rec("G", arrayRGB[0][1]);
	rec("B", arrayRGB[0][2]);
	cout << mina;
}

DP Solution

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
#include <map>

using namespace std;
int n = 1;
int arrayRGB[1001][3];
int arrayDP[1001][3];
int cnt = 0;
void rec(int v, int c) {
	cnt++;
	if (v > 0) {
		int aa;
		int bb;
		if (arrayDP[v-2][(c + 1) % 3] != 0) {
			aa = arrayDP[v-2][(c + 1) % 3];
		}
		else {
			rec(v - 1, (c + 1) % 3);
			aa = arrayDP[v - 2][(c + 1) % 3];
		}

		if (arrayDP[v-2][(c + 2) % 3] != 0) {
			bb = arrayDP[v-2][(c + 2) % 3];
		}
		else {
			rec(v - 1, (c + 2) % 3);
			bb = arrayDP[v - 2][(c + 2) % 3];
		}
		arrayDP[v-1][c] = min(aa, bb) + arrayRGB[v-1][c];
	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int r, g, b;
		cin >> r >> g >> b;
		arrayRGB[i][0] = r;
		arrayRGB[i][1] = g;
		arrayRGB[i][2] = b;

	}
	arrayDP[0][0] = arrayRGB[0][0];
	arrayDP[0][1] = arrayRGB[0][1];
	arrayDP[0][2] = arrayRGB[0][2];
	rec(n ,0);
	rec(n, 1);
	rec(n, 2);
	cout << min(arrayDP[n - 1][0], min(arrayDP[n - 1][1], arrayDP[n - 1][2]));
}