[BaekJoon/C] No.1149 : RGB거리

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

No.1149 문제

 

문제해석

 

1. N번 집의 색과 N-1번 집의 색이 달라야한다.(1번 2번 포함) => 직접색과 다르게 진행해야됩니다.
2. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. => 3가지의 색이 겹치지 않게 배정해야됩니다.
3. 집 색칠 비용의 최소값을 구해야됩니다.

// 각 집의 칠하는 비용을 입력받고 최소비용을 계산합니다
for (i = 1; i <= N; i++) 
	{
		scanf("%d %d %d", &arr[0], &arr[1], &arr[2]); 
		dp2[0] = dp[0];
		dp2[1] = dp[1];
		dp2[2] = dp[2];
		dp[0] = Min(dp2[1], dp2[2]) + arr[0]; 
		dp[1] = Min(dp2[0], dp2[2]) + arr[1];
		dp[2] = Min(dp2[0], dp2[1]) + arr[2];
	}

 

 

사용자에게 각 집을 칠하는 비용을 입력받습니다.

dp2에 현재 최소비용인 dp값을 임시저장한 뒤 

dp의 최소 비용을 임시저장했던 dp2을 비교하며 최소비용을 갱신해줍니다.

이를 N번 반복하면 각각의 색상의 최소비용을 구할 수 있습니다.

 

=>  0번째(빨간색)은 초록색과 파란색 배열 중 작은 값과 이전에 계산된 dp값에 더하고 빨간색을 제외한 초록색과 파란색또한 나머지 색상비용과 비교하여 구해줍니다.

 

소스코드 & 문제풀이

 

#include <stdio.h>

int arr[3]; // 집을 칠할 때 드는 비용을 저장하는 배열입니다
int dp[3]; // 최소 비용을 저장하는 배열입니다
int dp2[3]; // 값을 계산하는 과정에서 비용을 임시로 저장하는 배열입니다 
int Min(int a, int b)
{
	return a < b ? a : b; //a가 b보다 작은 조건이 참이면 a를 반환하고 거짓이면 b를 반환합니다
}
void distance_RGB(int N)
{
	int i;
	dp[0] = dp[1] = dp[2] = 0;
	
    // 각 집의 칠하는 비용을 입력받고 최소비용을 계산합니다
    for (i = 1; i <= N; i++) 
	{
		scanf("%d %d %d", &arr[0], &arr[1], &arr[2]); 
		dp2[0] = dp[0];
		dp2[1] = dp[1];
		dp2[2] = dp[2];
		dp[0] = Min(dp2[1], dp2[2]) + arr[0]; 
		dp[1] = Min(dp2[0], dp2[2]) + arr[1];
		dp[2] = Min(dp2[0], dp2[1]) + arr[2];
	}
	int min = Min(Min(dp[0], dp[1]), dp[2]);
	printf("%d", min);
}
int main()
{
	int i;
	int N;
	scanf("%d", &N);
	distance_RGB(N); // 함수 호출하여 전체 계산을 수행하고 최소 비용을 출력합니다
}

 

 

예제 입출력 결과

 

 

 

 

https://velog.io/@kimmainsain/C%EC%96%B8%EC%96%B4-%EB%B0%B1%EC%A4%80-1149-RGB%EA%B1%B0%EB%A6%AC