[백준/C++] RGB거리_1149

📝 문제

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

💻 코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int arr[1001][3];
int dp[1001][3];

void dpp() {	
	
	// n번집은 n-1집의 색과 다르다.
	int home = 1;
	while(home != n){
		for (int color = 0; color < 3; color++) {
			for (int i = 0; i < 3; i++) {
				if (i == color) continue;	// i번째집은 i+1, i-1의 집과 색이 다르다.
				if (!dp[home][color]) dp[home][color] = dp[home - 1][i] + arr[home][color];
				else
					dp[home][color] = min((dp[home - 1][i] + arr[home][color]), dp[home][color]);
			}
		}
		
		home += 1;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;

	//vector<vector<int>> arr(n, vector<int>(3, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 3; i++) {
		dp[0][i] = arr[0][i];
	}
	dpp();
	int ans = min(dp[n - 1][0], dp[n - 1][1]);
	ans = min(ans, dp[n - 1][2]);
	
	

	cout << ans;

	return 0;
}

💡 Point

dfs로 시작했지만, 시간초과가 발생했다. 그래서 dp를 적용시켰더니 해결!
dp가 아직 익숙하지 않아서 문제를 많이 solve 해야겠다.