boj, 백준) 1149. RGB거리 ( C / C++)

1. 문제 링크

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

1149번: RGB거리

2. 문제 개요

1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

 

i. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

ii. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

iii. 2~n-1번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

 

3. 문제 힌트

Bottom - up으로 문제를 해결한다.

각 index의 dp값을 현재 index번째 집까지의 최솟값이라고 설정.

현재의 최솟값은 이전 최솟값을 사용하면 최솟값이 된다.

 

4. 문제 풀이

 

dp배열을 정의하자

dp[index][3]으로 두자.

첫 번째의 index는 i번째 집을 나타낸다. 두 번째의 [3]은 빨간색, 초록색, 파란색이다.

다음은 1번째 집을 모두 각각의 색깔로 칠했을때의 경우이다.

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

 

이제 2번째 집의 경우를 살펴보자.

2번째 빨간색집은

1번째 초록색, 파란색 집만 고려하면 된다. 왜냐하면 2 가지 색을 연속적으로 칠할 수 없기 때문이다.

따라서 1번째 집의 최소비용은 최솟값(초록색, 파란색) + 1번째 빨간색 비용과 같다.

dp[2][0] = min(dp[1][1], dp[1][2]) cost[2][0];

이처럼 초록색, 파란색에도 똑같이 적용한다.

2번째 값이 정해졌다. 그럼 i번째에는 어떨까?

 

dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];

위의 코드와 같이 쓸 수 있겠다.

항상 현재의 최솟값은 이전 최솟값을 반영한다는 것을 기억하자.

 

 

5. 코드

(Bottom up)

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

int cost[1001][3];
int dp[1001][3];

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);

	//초기값 설정
	dp[1][0] = cost[1][0];
	dp[1][1] = cost[1][1];
	dp[1][2] = cost[1][2];

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

	int ans = min(min(dp[n][0], dp[n][1]), dp[n][2]);

	printf("%d", ans);

	return 0;
}

(Top - down)

 

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

int cost[1001][3];
int dp[1001][3];

int solution(int cur, int color)
{
	int &cache = dp[cur][color];
	if (cache != -1)	return dp[cur][color];

	if(color == 0)
		return dp[cur][color] = min(solution(cur - 1, 1), solution(cur - 1, 2)) + cost[cur][color];
	else if(color == 1)
		return dp[cur][color] = min(solution(cur - 1, 0), solution(cur - 1, 2)) + cost[cur][color];
	else
		return dp[cur][color] = min(solution(cur - 1, 0), solution(cur - 1, 1)) + cost[cur][color];
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);

	memset(dp, -1, sizeof(dp));
	dp[1][0] = cost[1][0];
	dp[1][1] = cost[1][1];
	dp[1][2] = cost[1][2];
	printf("%d", min(solution(n,0),min(solution(n,1),solution(n,2))));

	return 0;
}

지적, 댓글 언제나 환영입니다~