[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - RGB 거리 (1149)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - RGB 거리 (1149)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - RGB 거리 (1149)

 

---

 

1149번: RGB거리

[ 문제 ]

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[ 입력 ]

• 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[ 출력 ]

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

[ 코드 ]

#include<iostream>
#include<algorithm> // min,max인자가 3개 이상이면 써줘야 오류가 안뜸 (일반적으로 그냥 써주자)
using namespace std;

int dp[1001][3];
// n개의 집을 칠하는 최소비용. 마지막 색깔은 i. (0은 red, 1은 green, 2는 blue)
int col[1001][3];
// n번째 집의, 색깔마다의 비용. (0은 red, 1은 green, 2는 blue)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N; // 집의 수
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> col[i][j];
			// i번째 집의, j (red / green / blue) 가격
		}
	}

	for (int i = 1; i <= N; i++)
	{
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + col[i][0]; // 마지막 색깔이 red
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + col[i][1]; // 마지막 색깔이 green
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + col[i][2]; // 마지막 색깔이 blue
	}


	cout << min({ dp[N][0], dp[N][1], dp[N][2] }); // 인자가 3개 이상이면 이와 같이 해줘야함.

	return 0;

}