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보다 작거나 같은 자연수이다.

예제 입력 및 출력

입력

3

26 40 83

49 60 57

13 89 99

 

출력

96

소스 코드

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int N;
long long cost[1001][3]; //색상별 가격
long long cache[1001][3];

long long Calculate(int house_num, int color) {
	long long nextcost = 2147483647;
    
	//기저사례
	if (cache[house_num][color] != -1)
		return cache[house_num][color];

	//함수 탈출 조건 - 마지막 집이면 탈출
	if (house_num == N)
		return cache[house_num][color] = cost[house_num][color];
	
	//현재 집 칠하는 비용
	cache[house_num][color] = cost[house_num][color];
	//재귀 호출
	for (int i = 0; i < 3; i++) {
		if (color != i) //현재 색상은 다음에 칠할 수 없다
			nextcost = min(nextcost, Calculate(house_num + 1, i));
	}
	return cache[house_num][color] += nextcost;
}

int main(void) {
	long long total = 2147483647;
	cin >> N;

	memset(cache, -1, sizeof(cache));

	//비용 입력받기
	for(int i = 1; i <= N; i++) 
		scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);

	for (int i = 0; i < 3; i++) {
		total = min(total, Calculate(1, i));
	}

	cout << total;
	
}

문제 풀이

1. cache값 설정

• cache[house_num][color] : house_num번째 집에 color색생을 칠했을 때 나올 수 있는 가격의 최솟값

2. 재귀 호출

• 현재 집에 RGB중 한 가지 색상을 칠하면 다음 집에는 현재 집에 칠한 색상을 제외하고 2가지 색상을 칠할 수 있다. -> 2가지 색상을 칠했을 때 얻게 되는 비용의 최솟값과 현재 집의 비용을 더함

3. 함수 탈출 조건

• 호출된 재귀함수의 인자가 N번째 집이면 해당 색상을 칠할 때 비용을 반환한다.

 

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