[C] 백준 - 1149번: RGB거리

3월 10일(금) - 동적계획법 1 (1149번)

1149번: RGB거리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- N개의 집을 각각 빨강,초록,파랑으로 칠하는 비용은 2차원 배열인 color_cost[1001][4]로 입력받음

- 각각의 집에서 생긴 누적비용은 dp[i][1]

- 첫번째 집은 누적비용이 없기 때문에 dp[1][1], dp[1][2], dp[1][3] 에 해당하는 color_cost 값을 그대로 넣는다

- 이후 dp[i][1] 값은 (직전 집에서 초록을 칠한 dp[i-1][2] 과 직전 집에서 파랑을 칠한 dp[i-1][3] 중 더 작은 값) +

  (해당 집을 빨강으로 칠하는 비용인 color_cost[i][1]) 으로 설정

- dp[i][2]와 dp[i][3]도 위의 과정과 동일한 형식으로 진행

- 최종적으로 3가지의 dp[N][1], dp[N][2], dp[N][3] 값들 중에서 가장 작은 값을 low_cost로 선언 및 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

for (int i = 2; i < N + 1; i++)
	{
		dp[i][1] = color_cost[i][1] + MIN(dp[i - 1][2], dp[i - 1][3]);
		dp[i][2] = color_cost[i][2] + MIN(dp[i - 1][1], dp[i - 1][3]);
		dp[i][3] = color_cost[i][3] + MIN(dp[i - 1][1], dp[i - 1][2]);
	}

1. 위의 풀이과정을 최종풀이의 일부이며 제대로 된 풀이이다

하지만 해당 파트의 코드를 처음 작성할때, 등호 오른쪽에서 color_cost 와 dp를 서로 바꾸어서 잘못 작성했었다

-> 동적계획법이니까! MIN을 통해서 비교되어야하는 값은 이미 입력받은 color_cost 가 아니라 갱신되고있는 dp 이다

-> 이후의 다른 동적계획법 문제를 보면, 지금의 풀이가 기본적인 구조가 되어야 하므로 헷갈리지 말아야한다

 

#define MIN(x,y) (x < y) ? (x) : (y)

2. 

입력된 2개의 color_cost 중에서 더 작은 값을 구하는 과정을 아래와 같이 처리했지만,

예제 1번부터 5번까지 모두 첫번째 줄의 R,G,B 3개의 값 중 가장 작은값만 출력되고 있는 상황

-> 더 작은 값을 구하는 과정을 매크로가 아닌 함수로 수정했더니 모든 예제에서 정확한 출력값이 나옴

-> 가장 마지막 최솟값인 low_cost를 구하는 과정때문에, 매크로가 아닌 함수를 이용해야 제대로된 결과가 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
//#define MIN(x,y) (x < y) ? (x) : (y)

#include <stdio.h>

int MIN(int x, int y)
{
	return ( (x < y) ? x : y );
}

int main(void)
{
	int color_cost[1001][4];
	int dp[1001][4];
	
	int N;
	scanf("%d", &N);

	for (int i = 1; i < N + 1; i++)
	{
		scanf("%d %d %d", &color_cost[i][1], &color_cost[i][2], &color_cost[i][3]);
	}

	dp[1][1] = color_cost[1][1];
	dp[1][2] = color_cost[1][2];
	dp[1][3] = color_cost[1][3];
	for (int i = 2; i < N + 1; i++)
	{
		dp[i][1] = color_cost[i][1] + MIN(dp[i - 1][2], dp[i - 1][3]);
		dp[i][2] = color_cost[i][2] + MIN(dp[i - 1][1], dp[i - 1][3]);
		dp[i][3] = color_cost[i][3] + MIN(dp[i - 1][1], dp[i - 1][2]);
	}

	int low_cost = MIN( MIN(dp[N][1], dp[N][2]), dp[N][3] );
	printf("%d", low_cost);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ