[dp] 1149. RGB 거리

#include <iostream>
using namespace std;

int dp[3][1010];
int A[3][1010];
int ans = 500000;
int min(int x, int y)
{
	if (x < y)return x;
	return y;
}
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> A[j][i];
		}
	}

	//bottom up
	dp[0][0] = dp[1][0] = dp[2][0] = 0;
	dp[0][1] = A[0][1]; dp[1][1] = A[1][1]; dp[2][1] = A[2][1];
	dp[0][2] = min(dp[1][1], dp[2][1]) + A[0][2];
	dp[1][2] = min(dp[0][1], dp[2][1]) + A[1][2];
	dp[2][2] = min(dp[0][1], dp[1][1]) + A[2][2];
	for (int i = 3; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (j == 0)
				dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + A[0][i];
			else if (j == 1)
				dp[1][i] = min(dp[0][i - 1], dp[2][i - 1]) + A[1][i];
			else
				dp[2][i] = min(dp[1][i - 1], dp[0][i - 1]) + A[2][i];
		}
	}

	for (int i = 0; i < 3; i++)
		ans = min(dp[i][n], ans);

	cout << ans << endl;
}

1. 문제 해결 전략

dp 문제는 무조건 Bottom Up 방식으로 해결하기로 결정했다.

(이유는 재귀를 아직 잘 못써먹겠어서..)

 

해당 문제는 정답률이 50%에 육박하는 쉬운 문제에 해당한다.

잡소리는 던져버리구 ..

 

먼저 bottom up으로 전략을 잡았다면 n번째 경우에 대해서 생각을 하자.

n번째 집에 칠하는 색깔은 n-1번째 집의 색깔과 연관이 있다.

같은색으로 칠할 수 없기 때문에 n번째 집에 칠하는 색깔은 n-1번째 집의 색깔과 달라야 한다는 조건

 

그리고, 이 문제는 순서와 색깔 두 가지의 상태가 존재하기 때문에 2중 dp문제라고 할 수 있겠다.

결과로서 최소 비용을 구한다는 점도 잊지말자.

대략의 점화식을 생각 했을 때

dp[m1][n] = min(dp[m2 or m3][n-1],dp[m3 or m2][n-1]) + A[m1][n]
dp[m2][n] = min(dp[m1 or m3][n-1],dp[m3 or m1][n-1]) + A[m2][n]
dp[m3][n] = min(dp[m1 or m2][n-1],dp[m2or  m1][n-1]) + A[m3][n]

// m은 색깔의 경우 , n은 집의 순서다

이런 식으로 생각할 수 있다.

좌변의 식이 n번 째 집이라면 우변의 식은 n-1번 째 집이 선택할 수 있는 경우로서

n번 째 집이 선택하지 않은 색깔중에 하나를 고르고 n-1번 째까지의 비용이 최소가 되는것을 찾는다.

마지막으로 n번째 집의 특정 색일 때 가격을 더해주면 점화식은 끝난다.

 

단, 위의 세가지 점화식은 경우에 따라 각각 나누어 사용해야 하는데

n번 째 집의 색을 결정하는 j돌림 반복문에서 결정하면 되겠다.

 

2. 걸린 시간

대략 15분정도 걸렸다.. 해당 문제를 2중 dp를 쓰냐 단일 dp를 쓰냐에서 시간이 좀 걸렸었던 것 같다.

 

3. 느낀점

이전의 dp문제들을 계속 틀리다가 오랜만에 맞추어서 기분이 굉장히 좋았다 ㅎㅎ!

 

4. 링크

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