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

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

1149번: RGB거리

---

#include <stdio.h>  // RGB거리

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

int arr[1001][4];
int dp[1001][4];

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}

	dp[1][1] = arr[1][1];
	dp[1][2] = arr[1][2];
	dp[1][3] = arr[1][3];

	for (int i = 2; i <= n; i++)
	{
		dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + arr[i][1];
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + arr[i][2];
		dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][3];
	}
	int MIN = 1000 * n + 1;
	MIN = min(min(dp[n][1], dp[n][2]), dp[n][3]);
	printf("%d", MIN);

	return 0;
}

---

MEMO

-- 현재의 배열과 바로 이전의 배열 중 겹치지 않는 열(인덱스)의 값을 각각 더한 후 최솟값을 저장

 

!! DP 풀이의 감을 어느정도 익힌 느낌 !!