[백준 1149번 / C++] RGB거리

dp배열을 생성해서 풀면 된다. 

 

#접근방법 

1. 2차원 dp 배열 생성한다. 

2. 현재 dp값에 이전 dp 배열에서 다른 색을 가지고 있는 집들 중 작은 값을 선택해서 더해준다.

3. 최솟값 출력한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std; 
vector <vector<int>> v;
int n; 
int result = INT_MAX; 

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n;		
	vector <vector <int>>dp(n + 1, vector<int>(3, 0)); 
	for (int i = 1; i <= n; i++) {
		cin >> dp[i][0] >> dp[i][1] >> dp[i][2]; 
		dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]); 
		dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]); 
		dp[i][2] += min(dp[i - 1][0], dp[i - 1][1]); 
	}
	cout << min(dp[n][0], min(dp[n][1], dp[n][2])); 
}

 

1149번: RGB거리