백준 1149 - RGB거리

문제 번호: 1149

문제 제목: RGB거리

문제 주소: https://www.acmicpc.net/problem/1149

문제 내용

1. 집은 일렬로 쭉 늘어서 있다. 단, [0]과 [N - 1]은 인접하지 않았다.
2. 인접한 집의 색이 동일하지 않아야 한다. (RRG는 불가능, RGR은 가능)
3. 입력으로 각 집의 RGB에 대한 도색 비용이 주어진다.
위 조건에 맞춰 [0]부터 [N - 1]번째 집까지 도색하는 비용의 최소값을 출력한다.

테스트 케이스

3 26 40 83 49 60 57 13 89 99	96
1 26 40 83	26

문제 풀이

비용이 최소인 경로를 구하는 문제. 이런 종류의 문제는 각 출발지에서 목적지까지 도달한 후에 경로별 값을 비교하는 것으로 구할 수 있다.
[1]의 R은 [0]의 G, B와 비교하여 작은 값과 더하고, [1]의 G는 [0]의 R, B와 비교, [1의 B는 [0]의 R, G와 비교하여 최소 값을 구하는 식으로 목적지인 [N-1]까지 최소 합계를 구하고, [N-1]의 R, G, B 중에서 가장 작은 값을 출력하는 것으로 해결할 수 있다.

풀이 코드

#include <iostream>
using namespace std;
// 배열을 사용한 풀이
void BAEKJOON_1149()
{
	int N;
	cin >> N;
	int* R = new int[N];
	int* G = new int[N];
	int* B = new int[N];
	/*----------------값 입력 받기-------------------*/
	for (int i = 0; i < N; ++i)
	{
		cin >> R[i] >> G[i] >> B[i];
	}
	/*-----------------비용 계산----------------------*/
	for (int i = 0; i < N - 1; ++i)
	{
		R[i + 1] += G[i] < B[i] ? G[i] : B[i];
		G[i + 1] += R[i] < B[i] ? R[i] : B[i];
		B[i + 1] += R[i] < G[i] ? R[i] : G[i];
	}
	int result = R[N - 1] < G[N - 1] ? R[N - 1] :G[N - 1];
	result = result < B[N - 1] ? result : B[N - 1];
	cout << result << endl;
	/*-------------------메모리 해제------------------*/
	delete[] R;
	delete[] G;
	delete[] B;
	return;
}

#include <iostream>
using namespace std;
// 배열을 사용하지 않는 풀이
void BAEKJOON_1149()
{
	int N;
	cin >> N;
	int R = 0;
	int G = 0;
	int B = 0;
	for (int i = 0; i < N; ++i)
	{
		int r, g, b;
		cin >> r >> g >> b;
		r = G < B ? r + G : r + B;
		g = R < B ? g + R : g + B;
		b = G < R ? b + G : b + R;
		R = r;
		G = g;
		B = b;
	}
	int minCost = R < G ? R : G;
	minCost = minCost < B ? minCost : B;
	cout << minCost << endl;
	return;
}