[C] 백준 1149 : RGB 거리

 

 

 

1. 문제

 

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 

2. 접근

 

이 문제는 n개의 집을 R, G, B를 이용해 이웃과 겹치지 않게 칠하는데 드는 최소 비용을 구해야 한다.

n번째까지 드는 비용을 구한 후 3개 중 최소 비용을 찾아내야 한다.

 

먼저 값을 입력받는 배열 input[1001][3]을 선언한 다음,

input[i][0], input[i][1], input[i][2] 에서 i번째 집을 칠했을 때의 최소 비용을 구한다. (0, 1, 2는 각각 R, G, B를 나타냄)

2번째 집을 칠할 때는 1번째 집을 칠한 비용을 포함해야 하며, 3번째 집을 칠할 때는 2번째 집을 칠한 비용을 포함해야 한다.

(2번째 집을 칠한 비용은 1번째 집을 칠한 비용도 포함되어 있음)

 

쉽게 나타내면 아래와 같다.

 

dp[i][0] = 최소값(dp[i-1][1], dp[i-1][2]) + 현재 색깔의 비용
dp[i][1] = 최소값(dp[i-1][0], dp[i-1][2]]) + 현재 색깔의 비용
dp[i][2] = 최소값(dp[i-1][0], dp[i-1][1]]) + 현재 색깔의 비용

 

마지막으로 최종으로 구한 3개의 값을 구해 최소 비용을 출력하면 된다.

 

문제에 나와있는 예시로 쉽게 보자면,

 

	input[i][0]	input[i][1]	input[i][2]
i=1	dp[1][0] = min(dp[0][1],dp[0][2])+26 = 26	dp[1][1] = min(dp[0][0],dp[0][2])+40 = 40	dp[1][2] = min(dp[0][0],dp[0][1])+83 = 83
i=2	dp[2][0] = min(dp[1][1],dp[1][2])+49 = 89	dp[2][1] = min(dp[1][0],dp[1][2])+60 = 86	dp[2][2] = min(dp[1][0],dp[1][1])+57 = 83
i=3	dp[3][0] = min(dp[2][1],dp[2][2])+13 = 96	dp[3][1] = min(dp[2][0],dp[3][2])+89 = 172	dp[3][2] = min(dp[2][0],dp[2][1])+99 = 185

 

3. 정답

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int dp[1001][3];
int input[1001][3]; // 입력받을 배열

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}


int main() {
	int n;
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf_s("%d %d %d", &input[i][0], &input[i][1], &input[i][2]);
	}

	dp[0][0] = input[0][0];
	dp[0][1] = input[0][1];
	dp[0][2] = input[0][2];

	for (int i = 1; i < n; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
	}

	printf("%d", min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]));
}