백준 알고리즘 1932번: RGB거리 [C++]

문제 출처: www.acmicpc.net/problem/1149

1149번: RGB거리

1. 코드

#include <iostream>
#define MAX 9999999

using namespace std;

int rgb[3][1000];
int last[3][1000];
int N;
int low = 9999999;

void solution(int deep, int check, int sum)
{
	if (deep == N)
	{
		if (low > sum)
			low = sum;
		return;
	}

	for (int i = 0; i < 3; i++)
	{
		if (check == i) continue;	//이전의 색과 동일하다면 다른 색 선택
		else if (last[i][deep] <= sum + rgb[i][deep]) continue;	// 같은 위치에 이전에 입력된 것이 더 작을 경우
		else last[i][deep] = sum + rgb[i][deep];
		solution(deep + 1, i, last[i][deep]);
	}
}
int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> rgb[j][i];
			last[j][i] = MAX;
		}
	}
	solution(0, 3, 0);
	cout << low;
	return 0;
}

(실행)

2. 풀이

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> rgb[j][i];
			last[j][i] = MAX;
		}
	}
	solution(0, 3, 0);
	cout << low;
	return 0;
}

일단 입력받을 것을 입력을 전부 받는데 동일한 인덱스 위치에 last배열도 MAX값으로 초기화를 진행한다. 그리고 solution을 실행을 하는데 처음에는 체크할 요소가 없기 때문에 0~2 중의 수가 아닌 3을 대입하여 조건문이 동작하지 않도록 해준다. 그리고 함수가 종료가 되면 low 즉, 가장 작은 수가 출력이 된다.

void solution(int deep, int check, int sum)
{
	if (deep == N)
	{
		if (low > sum)
			low = sum;
		return;
	}

	for (int i = 0; i < 3; i++)
	{
		if (check == i) continue;	//이전의 색과 동일하다면 다른 색 선택
		else if (last[i][deep] <= sum + rgb[i][deep]) continue;	// 같은 위치에 이전에 입력된 것이 더 작을 경우
		else last[i][deep] = sum + rgb[i][deep];
		solution(deep + 1, i, last[i][deep]);
	}
}

그리고 solution이 실행이 되면 3가지의 색을 비교를 하는데 먼저 check와 i의 값이 동일하다면 이전의 색과 현재의 색이 동일하기 때문에 다른 색으로 바꾼다. 그리고 last [i][deep]의 값이 sum + rgb [i][deep]보다 작거나 같다면 굳이 더할 필요가 없기 때문에 시간을 효율적으로 사용하기 위해서 continue를 해준다. 그렇지 않다면 해당 값으로 초기화를 해주고 재귀 함수를 호출한다.

계속해서 재귀 함수가 호출이 되면 deep의 값이 증가하여 N과 동일해질 때 low 값이 sum보다 크다면 low의 값을 sum의 값으로 초기화를 진행해주고 반환을 해준다. 그렇게 해서 계속해서 합이 더 작은 경우를 도출해내는 것이다.

3. 느낀 점

브루트 포스와 백트래킹의 문제들을 풀면서 재귀 함수로 문제를 푸는 게 많이 능숙해졌는데 그다음에 동적 계획법으로 작성을 하려니 많이 어색하기도 하고 익숙해지지 않아서 아직 공부가 더 필요한 것 같다.