[BAEKJOON] 1149번 RGB거리

문 제

 

 

소 스  코 드

#include <iostream>
#include <algorithm>
constexpr int RED				{ 0 };
constexpr int GREEN				{ 1 };
constexpr int BLUE				{ 2 };


typedef long long INT;

struct RGB {
	INT R;
	INT G;
	INT B;
};

void Search_RGB(RGB *, const int&);

int main() {
	int N;

	std::cin >> N;

	RGB *home{ new RGB[N] };

	for (int i = 0; i < N; ++i) std::cin >> home[i].R >> home[i].G >> home[i].B;
	Search_RGB(home, N);

	delete[] home;

	return 0;
}


void Search_RGB(RGB * home, const int& N) {
	INT temp[3]{ home[0].R, home[0].G, home[0].B };
	INT next_temp[3]{};
	for (int i = 1; i < N; ++i) {
		next_temp[RED] = 	std::min(temp[GREEN], temp[BLUE]) + home[i].R;
		next_temp[GREEN] = 	std::min(temp[RED], temp[BLUE]) + home[i].G;
		next_temp[BLUE] = 	std::min(temp[GREEN], temp[RED]) + home[i].B;

		temp[RED] = 		next_temp[RED];
		temp[GREEN] = 		next_temp[GREEN];
		temp[BLUE] = 		next_temp[BLUE];
	}

	std::cout << std::min({ temp[RED], temp[GREEN], temp[BLUE] });
}

 

풀 이

 

• RED = MIN(이전 GREEN일 때 최소 누적값, 이전 BLUE일 때 최소 누적값) + 현재 RED

• GREEN = MIN(이전 RED일 때 최소 누적값, 이전 BLUE일 때 최소 누적값) + 현재 GREEN

• BLUE = MIN(이전 GREEN일 때 최소 누적값, 이전 RED일 때 최소 누적값) + 현재 BLUE

• 위의 경우 여러가지 경우의 수에서 최솟값을 알 수 있다.

 

실 수 했 던  사 항

#include <iostream>

constexpr int RED				{ 0 };
constexpr int GREEN				{ 1 };
constexpr int BLUE				{ 2 };

constexpr int MAX_BRUSH_HOME	{ 1'001 };

typedef long long INT;

struct RGB {
	int R;
	int G;
	int B;
};

void Search_RGB(bool *, RGB *, const int&, INT&);

int main() {
	int N;

	std::cin >> N;

	RGB *home{ new RGB[N] };
	bool RGB_tf[3]{ false, };
	INT temp{ 0 };

	for (int i = 0; i < N; ++i) std::cin >> home[i].R >> home[i].G >> home[i].B;

	for (int i = 0; i < N; ++i) {
		Search_RGB(RGB_tf, home, i, temp);
	}

	std::cout << temp;

	delete[] home;

	return 0;
}

void Search_RGB(bool * tf, RGB * home, const int& i, INT& tmp) {
	int index{ -1 };
	for (int i = 0; i < 3; ++i) {
		if (true == tf[i]) index = i;
	}

	INT temp{ MAX_BRUSH_HOME };

	if (-1 != index)	tf[index] = false;

	if (home[i].R < temp && (index != RED)) {
		temp = home[i].R;
		tf[RED] = true;
	}
	
	if (home[i].G < temp && (index != GREEN)) {
		temp = home[i].G;
		tf[RED] = false;
		tf[GREEN] = true;
	}
	
	if (home[i].B < temp && (index != BLUE)) {
		temp = home[i].B;
		tf[GREEN] = false;
		tf[BLUE] = true;
	}

	tmp += temp;
}

 

• 위의 경우 

  1 100 8

  4 50   999
  일 때 1 + 50 이 최솟 값이 되는데 하지만 실제 최솟값은 8 + 4 이기 때문에 잘못된 코드 이다.

 

결 과 값

 

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/1149