C++)백준 1149번 풀이 _ RGB 거리

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

1149번: RGB거리

학부생때도 제대로 해본 적 없는 DP...

일단 문제를 많이 풀어보라는 게 이런 의미였구나 하고 체감하는 중.

이런 류의 문제는 지금 느끼기엔 일단.. 기준을 어떻게 두고 구할 것인지를 찾는게 중요한 것 같다

그게 안 익숙해서 접근하기가 힘들다 ㅜ;;

 

아래와 같은 input이 있다고 가정 할 때,

26	40	83
49	60	57
13	89	99

각 집에 각 색을 칠하려고 할 때 최소 비용을 계산한다.

첫번째 집은 아무 색이나 칠할 수 있으니 그냥 각 색 비용 그대로.

26	40	83

 

2번째 집에 빨간색을 칠하려고 할 때의 비용을 계산하려고 할 때 나올 수 있는 케이스는

빨간색이 아닌 색인 파란색/초록색이 앞집일 경우인데

그 중 앞집에 초록색을 칠한 비용이 더 작으니까

거기에 현재 빨간색을 칠할 비용을 더하면 최소값이 나온다.

-> 40 + 49 = 89

이런 식으로 계산하면 둘째 줄은 아래와 같은 값을 채울 수 있다.

26	40	83
89	86	83

그리고 3번째 집에 빨간색을 칠하려고 할 때는, 그 앞 단계는 볼 필요 없고

2번째 집까지 칠했을 때의 비용만 보고 계산한다 <- 중요

26	40	83
89	86	83
96	172	185

그렇게 .. 생각해보면

n번째 집에 각 색r을 칠하려고 할 때, 최소 비용은

n-1번째 집의 g와 b를 칠하는 최소 비용 중 더 작은놈을 골라서 n번째 집에 r을 칠하는 비용을 더한 값

 

 

그렇게 계산해서 맨 끝에 rgb 중 최소 값을 뽑게

코드를 짜면 됩니다.

#include<stdio.h>
#include<algorithm>

using namespace std;

int main(void) {
	int i, cnt;
	int rgb[3] = { 0 };
	int minSum[1000][3] = { 0 };

	scanf("%d", &cnt);
	scanf("%d %d %d", &rgb[0], &rgb[1], &rgb[2]);
	
	minSum[0][0] = rgb[0];
	minSum[0][1] = rgb[1];
	minSum[0][2] = rgb[2];

	for (i = 1; i < cnt; ++i)
	{
		scanf("%d %d %d", &rgb[0], &rgb[1], &rgb[2]);
		minSum[i][0] = min(minSum[i - 1][1], minSum[i - 1][2]) + rgb[0];
		minSum[i][1] = min(minSum[i - 1][0], minSum[i - 1][2]) + rgb[1];
		minSum[i][2] = min(minSum[i - 1][0], minSum[i - 1][1]) + rgb[2];
	}

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