<Baekjoon>#1149 RGB 거리 (RGB street) c++

먼저 dp[N][3] 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다.
dp[0][0]= 1번 집이 R를 색칠했을 경우 비용의 최솟값,
dp[0][1]= 1번 집이 G를 색칠했을 경우 비용의 최솟값,
dp[0][2]= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장한다

먼저 처음 dp에 각 집을 R,G,B로 칠하는 비용을 입력받으면서 저장한다.

void input() {
	cin >> N;
	if (N > MAX)
		exit(EXIT_FAILURE);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> dp[i][j];
}

그 다음 dp[0][i] 일 때 값들은 그대로 두고
dp[1][i]값들을 차례로 생각해본다.
dp[1][0]에는 두 번째 집이 R로 칠해졌을 경우이므로, 첫 번째 집이 R이면 안 된다. 그래서 (첫 번째 집이 G로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우) 와 (첫 번째 집이 B로 칠해졌을 경우 + 두 번째 집이 R로 칠해질 경우)중 더 작은 값을 저장한다.

#include<iostream>
#include<algorithm>

const int MAX = 1001;
int dp[MAX][3];
int N;

using namespace std;

void input() {
	cin >> N;
	if (N > MAX)
		exit(EXIT_FAILURE);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> dp[i][j];
}
int paintRGB() {
	
	for (int i = 1; i < N; i++) {
		dp[i][0] = min(dp[i - 1][1] + dp[i][0], dp[i - 1][2]+dp[i][0]);
		dp[i][1] = min(dp[i - 1][0] + dp[i][1], dp[i - 1][2] + dp[i][1]);
		dp[i][2] = min(dp[i - 1][0] + dp[i][2], dp[i - 1][1] + dp[i][2]);
	}
	return min({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]});
}
int main() {

	input();
	cout << paintRGB() << endl;

	return 0;
}

좋은 웹페이지 즐겨찾기