[BAEKJOON] 17404번 : RGB 거리 2

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>
constexpr int MAX{ 1'000'001 };

int dp[1001][3];
int RGB[1001][3];

int main() {
	int N;
	std::cin >> N;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			std::cin >> RGB[i][j];
		}
	}

	int answer{ MAX };
	// 첫 번째 집의 색
	for (int i = 0; i < 3; ++i) {

		// 선택된 집의 색상 고정
		for (int j = 0; j < 3; ++j) {
			if (j == i) dp[0][j] = RGB[0][j];
			else		dp[0][j] = MAX;
		}

		for (int j = 1; j < N; ++j) {
			// j - 1번째 집까지 색을 칠하는 최솟값 + j번째 집을 R으로 칠하는 비용
			dp[j][0] = std::min(dp[j - 1][1], dp[j - 1][2]) + RGB[j][0];
			// j - 1번째 집까지 색을 칠하는 최솟값 + j번째 집을 G으로 칠하는 비용
			dp[j][1] = std::min(dp[j - 1][0], dp[j - 1][2]) + RGB[j][1];
			// j - 1번째 집까지 색을 칠하는 최솟값 + j번째 집을 B으로 칠하는 비용
			dp[j][2] = std::min(dp[j - 1][0], dp[j - 1][1]) + RGB[j][2];
		}

		for (int j = 0; j < 3; ++j) {
			if (i == j) continue;
			answer = std::min(answer, dp[N - 1][j]);
		}
	}

	std::cout << answer << '\n';

	return 0;
}

 

풀 이

 

• [ 백준 ] 1149번 : RGB거리

 

출 력 값

 

 

문 제  출 처

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

17404번: RGB거리 2