[C언어] 백준 1149 : RGB거리

생각의 흐름

문제를 먼저 이해해보자.

1. 계속 엇갈려야된다. (직전색과 다르면 된다.)

2. 입력값을 활용하려면 2차원배열을 사용해야겠다.

3. 합을 구해야 하므로 sum을 사용해야겠구나

4. 동적 계획법을 쓰려면 저장해야되는 배열을 만들어놔야겠다.

그런데 1번을 어떻게 작성해야되는지 정말 모르겠다. 심지어 최솟값을 구해야되는데, 이거는 어떻게 구해야하나 막막했다. 재귀로 끝까지 구하고 sum값 중 min을 구하면 되겠지만, 이러면 무조건 타임아웃이 날 것이다. 동적계획을 안썼기 때문에..

문제점

• 직전색과 다르게 진행하는 방법
• 최솟값을 구하는 방법
• 동적 계획법을 사용하는 방법

그냥 문제를 어떻게 푸는지 모르는거다 저거 3개를 몰랐으니..

결국 검색을 해서 받아들이기로 했다.. 코드작성 시작도 못했다.. 진짜 몰라서 못했다.

다른 사람 코드 1

#include <stdio.h>

int arr[3];
int dp[3];
int dp2[3];
int Min(int a, int b)
{
	return 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://evga7.tistory.com/52 코드를 이해하기엔 이 분 코드가 더 나았다.

처음엔 26 40 83 을 받는다 그이후
같은 색은 못칠하므로 그다음 번째에서 0번째(R)는 1,2 번째(G,B) 배열중 작은값과 이전에 계산된 dp값에 더하면된다.
1번째는 0,2 번째와 2번째는 0,1번째와 비교하여 그전의 dp값과 계속 비교하면서 구하면된다.
처음엔 dp에 26 40 83 이 저장될것이다 그전의 계산된 값이 없으므로
그다음엔 dp[0] 에는 dp[1],dp[2] 값중 더 작은값과 R값을 더한다.
나머지도 그런식으로 계산하여 dp[0~~3] 값중 최소값을 출력하면 된다.

다른 사람 코드 2

#include <stdio.h>
#define MAX 1000*1000

int input[1001][4];
int dp[1001][4];

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

int main() {
	int N;
	scanf("%d", &N);
	
	// 입력
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= 3; j++)
			scanf("%d", &input[i][j]);
	
	// dp 배열 채우기
	dp[1][1] = input[1][1];
	dp[1][2] = input[1][2];
	dp[1][3] = input[1][3];

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

	// 출력
	int min = MAX + 1;
	for (int i = 1; i <= 3; i++)
		if (dp[N][i] < min)
			min = dp[N][i];
	printf("%d", min);
	return 0;
}

https://wisdom-990629.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-1149%EB%B2%88-RGB%EA%B1%B0%EB%A6%AC

i번째 집의 색깔을 정할 때, i-1번째 집을 확인합니다.
i번째 집 -> 빨간색(index 1)으로 칠하려면
i-1번째 집 -> 초록 색(index 2) 아니면 파란색(index 3)이어야 합니다.
따라서 i-1번째 집을 초록색, 파란색으로 칠했을 때의 비용 중 최솟값에 빨간색을 칠하는 비용을 더하면 됩니다.
=> dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + input[i][1]
즉, 각 집마다 빨간색, 초록 색, 파란색을 칠하는 경우를 모두 고려한 후 조건에 맞게 활용하는 것입니다.

{ }에 적힌 부분은 1번 집부터 선택한 색깔의 index 입니다.
(ex. dp[2][1] -> 1번 집 2번 index (초록 색), 2번 집 1번 index (빨간색) 선택)
이렇게 dp 배열을 채운 후 dp[N][1] ~ dp[N][3] 중 최솟값을 찾으면 됩니다!

진짜 너무어렵다 계속 봐야될 것 같다 그 뒤에 문제들도 한번씩 훑어봤는데 이 문제를 이해못하면 뒤에까지 영향을 미친다..

포인트는 그리드처럼 제일 작은값을 먼저 잡으면서 가면 틀린다는 것이다.
그리고 직전색과 다르게 선택하는 방법은 index - 1이 다른것을 고르는 것이다. 그중에서 최솟값을 지정해서 dp를 채우는 논리다.

아마 여기에 시간 좀 많이 갈아버릴 것 같다..