[백준 17404번 C/C++] RGB거리 2

 

[백준 17404번 C/C++] RGB거리 2

 

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

---

 

해결전략

 

동적계획법 Dynamic Programming (DP)

 

 

첫 번째 집을 각각 빨강, 초록, 파랑으로 칠하는 세 가지 경우를 각각 계산한다. 첫 번째 집을 특정 색으로 칠한 경우, 그 색을 제외한 다른 두 색의 비용은 계산할 수 없으므로 무한대(INF)로 설정한다.

• dp[1][0] = v[1].red;
  dp[1][1] = dp[1][2] = INF;

 

두 번째 집부터 마지막 집까지 각각의 집에 대해, 이전 집을 다른 두 색으로 칠했을 때의 최소 비용을 찾아 현재 집을 칠하는 비용과 더한다. 이렇게 해서 각 집마다 세 가지 색으로 칠했을 때의 누적 최소 비용을 계산한다. 

• dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i].red; )

 

마지막 집에 도달했을 때, 첫 번째 집에서 선택한 색을 제외한 나머지 두 색 중 더 낮은 비용을 최종 답안으로 선택한다. 이 과정을 세 번 반복하여 세 가지 경우 중 가장 낮은 최종 비용을 찾아낸다. 

• answer = min(answer, min(dp[n][1], dp[n][2]));

 

 

핵심코드

	dp[1][0] = v[1].red;
	dp[1][1] = dp[1][2] = INF;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i].red;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i].green;
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i].blue;
	}
    answer = min(answer, min(dp[n][1], dp[n][2]));

 

---

 

정답코드

 

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

const int INF = 1e9; // 최대값 2147000000로 사용하면 오버플로우 난다. 조심!

struct Color {
	int red; int green; int blue;
};

int n;
vector<Color> v;
vector<vector<int>> dp;

int answer = INF; // 정답을 저장할 변수. 초기값은 INF로 설정하여 최소값을 찾기 위한 기준점으로 사용

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n+1);
	dp.resize(n + 1, vector<int>(3, INF));
	for (int i = 1; i <= n; i++) {
		cin >> v[i].red >> v[i].green >> v[i].blue;
	}

	// 첫 번째 집을 Red으로 칠했을 때
	dp[1][0] = v[1].red;
	dp[1][1] = dp[1][2] = INF; // 첫 번째 집을 나머지 색깔로 칠했을 때의 비용은 사용할 수 없으므로 INF로 설정
	for (int i = 2; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i].red;	 // Red
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i].green; // Green
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i].blue;  // Blue
	}
	answer = min(answer, min(dp[n][1], dp[n][2]));

	// 첫 번째 집을 Green으로 칠했을 때
	dp[1][1] = v[1].green;
	dp[1][0] = dp[1][2] = INF;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i].red;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i].green;
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i].blue;
	}
	answer = min(answer, min(dp[n][0], dp[n][2]));

	// 첫 번째 집을 Blue으로 칠했을 때
	dp[1][2] = v[1].blue;
	dp[1][0] = dp[1][1] = INF;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i].red;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i].green;
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i].blue;
	}
	answer = min(answer, min(dp[n][0], dp[n][1]));

	cout << answer;

	return 0;
}

 

 

---

 

 

유사문제

 

2023.06.02 - [⭐ 코딩테스트/백준] - [백준 1149번 C/C++] RGB 거리

---