[백준 1149번] RGB거리

RGB거리 문제를 해결하는데 핵심은 전집까지 계산된 비용 중 자신과 같은 색깔을 제외한 나머지 두 집 중 적은 비용을 택하여 비용을 계산해야 한다는 것이다.

temp는 계산된 최소비용 값을 저장하는 배열이다. temp[n]은 0부터 n까지의 집비용의 최소값을 저장한것이다.
findMin은 직전 집에서 자신과 다른 색깔의 집 중 최소값을 반환하는 함수이다.

 

#include"stdio.h"

int temp[1000][3] = { 0 };


int findMin(int i, int j){
	int min = 100000000;
	for (int z = 0; z < 3; z++){
		if (z == j)
			continue;
		if (min > temp[i][z])
			min = temp[i][z];
	}
	return min;
}

int main(){
	int n;
	int a[1000][3] = { 0 };
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			scanf("%d", &a[i][j]);
		}
	}

	temp[0][0] = a[0][0];
	temp[0][1] = a[0][1];
	temp[0][2] = a[0][2];

	for (int i = 1; i < n; i++){
		for (int j = 0; j < 3; j++){
			temp[i][j] = findMin(i - 1, j) + a[i][j];
		}
	}

	int min = temp[n-1][0];
	
	for (int i = 1; i < 3; i++){
		if (min > temp[n-1][i]){
			min = temp[n-1][i];
		}
	}
	
	printf("%d",min);
}