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

알고리즘

 

• 다이나믹 프로그래밍

 

---

풀이

h 2차원 벡터를 두어 똑같은 색이 이웃하지 않도록 h[i-1]의 값 중 최소 값을 이용하여 값을 누적해간다.

 

즉, 

h[i][1]은 i번째 집을 빨간색으로 칠할 때의 최소 비용,

h[i][2]은 i번째 집을 초록색으로 칠할 때의 최소 비용,

h[i][1]은 i번째 집을 파란색으로 칠할 때의 최소 비용이 된다.

 

그러면 h[n][1], h[n][2], h[n][3] 중 최소값이 답이 된다.

 

---

성공 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, r, g, b, res;
	cin >> n;
	vector<vector<int> > h(n+1, vector<int>(4, 0));
	cin >> h[1][1] >> h[1][2] >> h[1][3];
	for(int i=2; i<=n; i++){
		cin >> r >> g >> b;
		for(int j=1; j<=3; j++){
			if(j==1){
				h[i][j]=r+min(h[i-1][2], h[i-1][3]);
			} else if(j==2){
				h[i][j]=g+min(h[i-1][1], h[i-1][3]);
			} else if(j==3){
				h[i][j]=b+min(h[i-1][1], h[i-1][2]);
			}
		}
 	}
	res=h[n][1];
	for(int i=1; i<=3; i++){
		res=min(res, h[n][i]);
	}
	cout << res;
	
	return 0;
}