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

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

1149번: RGB거리

#문제 간단 정리

문제 풀이 전략
문제의 목적은 주어진 규칙에 따라 연속된 집들을 서로 다른 색으로 칠하는 최소 비용을 찾는 것입니다. 이러한 유형의 문제는 동적 프로그래밍(dynamic programming, DP)을 사용하여 해결할 수 있습니다.

문제를 해결하는 전략은 다음과 같습니다:

먼저, 각 집을 칠할 때의 비용을 2차원 배열에 저장합니다.
그런 다음, 다른 색상 조합에 대해 이전 집들까지의 최소 비용을 저장하는 또 다른 2차원 배열을 만듭니다.
각 집에 대해 가능한 색상을 선택하고, 선택한 색상을 제외한 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.
모든 집을 확인한 후, 마지막 집에서 가능한 최소 비용을 찾습니다

 

#전체 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;


int main() {
	int n; cin >> n;
	int house_cost[1001][3] = { 0 };
	int result[1001][3] = { 0, };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> house_cost[i][j];
		}
	}

	result[0][0] = house_cost[0][0];
	result[0][1] = house_cost[0][1];
	result[0][2] = house_cost[0][2];

	for (int i = 1; i <= n; i++) {
		result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
		result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
		result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];

	}
	int min = 123456789;
	for (int i = 0; i < 3; i++) {
		if (result[n][i] < min) {
			min = result[n][i];
		}
	}
	cout << min << endl;
}

코드 해설
코드는 위에서 설명한 전략을 따르며, 주요 부분을 분석하겠습니다.

cpp
Copy code
int n; cin >> n;
int house_cost[1001][3] = { 0 };
int result[1001][3] = { 0, };
여기서 n은 집의 수를 나타내며, house_cost 배열에 각 집을 칠하는 비용을 저장합니다. result 배열은 각 집에 대한 최소 비용을 저장할 배열입니다.

cpp
Copy code
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> house_cost[i][j];
}
}
이 부분은 각 집을 칠하는 비용을 입력 받아 house_cost 배열에 저장하는 코드입니다.

cpp
Copy code
result[0][0] = house_cost[0][0];
result[0][1] = house_cost[0][1];
result[0][2] = house_cost[0][2];
여기에서 첫 번째 집의 최소 비용을 각 색상의 비용으로 초기화합니다.

cpp
Copy code
for (int i = 1; i <= n; i++) {
result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];
}
이 반복문은 동적 프로그래밍을 통해 각 집에서 가능한 최소 비용을 계산합니다. 현재 집의 각 색상에 대해 가능한 최소 비용을 찾기 위해 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.

cpp
Copy code
int min = 123456789;
for (int i = 0; i < 3; i++) {
if (result[n][i] < min) {
min = result[n][i];
}
}
cout << min << endl;
마지막으로, 마지막 집에서 가능한 최소 비용을 찾고 출력합니다.

주의사항
반복문의 범위를 주의해야 합니다. for (int i = 1; i <= n; i++)에서 i는 n까지 돌아야 하지만, 배열 인덱스는 0부터 시작하므로 house_cost와 result 배열에 접근할 때 i-1을 사용해야 합니다.

cpp
Copy code
for (int i = 1; i < n; i++) { // n까지가 아니라 n-1까지
...
result[i][0] = min(result[i-1][1], result[i-1][2]) + house_cost[i-1][0];
...
}
그리고 최종 결과를 찾을 때, result[n][i] 대신 result[n-1][i]를 사용해야 합니다.