1149번 RGB 거리

문제링크 : www.acmicpc.net/problem/1149

1149번: RGB거리

---

---

<풀이 참고>

 

1. 위에 조건이 3가지로 나와있지만, 결국은 모든 집에 있어 양 옆집과 색깔이 달라야한다는 뜻이다.

 

2. 앞서 같은 색을 몇 번 칠했든 양 옆집과 색이 다르고 최소값이면 채택.

 

 

 

 

<알고리즘>

 

1. 첫 번째 집부터 그 집이 R색일경우, G색일 경우, B색일 경우로 나눠 동시에 3가지 경우를 고려함

 

2. 0~N번째 집까지 자신의 색깔을 결정하는데 있어 앞집 색을 고려해 앞집과 같은 색의 경우를 제외한 두 색중 작은 값이었던 색의 경우를 이어가도록 채택

 

3. N번째 집까지 더했을 때 나오는 값은 모든 집의 색을 칠할때 앞집의 색을 고려한 경우이고, 앞집의 페이트 비용의 최소값+우리집 칠하는 색깔을 고려한 것이기에, dq[N]번째 행의 최소값을 찾아서 return

 

 

 

메모리 : 2016KB   시간 : 0ms

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	cin >> N;
	
	int price[1001][3] = { 0, };
	for (int i = 0; i < N; i++) {
		cin >> price[i][0] >> price[i][1] >> price[i][2];
	}

	int dq[1001][3] = { 0, };
	for (int i = 1; i <= N; i++) {
		dq[i][0] = price[i - 1][0] + min(dq[i - 1][1], dq[i - 1][2]);
		dq[i][1] = price[i - 1][1] + min(dq[i - 1][0], dq[i - 1][2]);
		dq[i][2] = price[i - 1][2] + min(dq[i - 1][0], dq[i - 1][1]);
	}

	cout << min(dq[N][0], min(dq[N][1], dq[N][2])) << "\n";
	return 0;
}

 

 

+) 참고 : yeodo95.tistory.com/24

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