백준 17404 RGB거리 2

RGB거리 2

이전에 봤던 문제 RGB거리와 거의 유사한 문제다. 조건 첫집과 마지막 집도 이웃이다만 추가되었다.
하지만 말이 이전에 봤던 문제지 거의 1년 전에 봤던 문제고, dp도 오랜만에 봐서 새로운 문제 느낌이었다.

문제분석

1. i는 i+1, i-1과 이웃이다.

   n번째 집을 기준으로 생각하기 때문에 i+1은 굳이 생각하지 않아도 된다.

2. 이웃은 같은 색을 칠할 수 없다.

   이번 집이 빨간색으로 칠하려면 이전 집이 초록이나 파랑을 칠해야 한다.
   여기서 점화식을 생각해볼 수 있다. d[n][2] = min(solve(n - 1, 0, first), solve(n - 1, 1, first)) + h[n][color];

3. 처음 집과 마지막 집은 이웃이다.

   조건이 까다롭다고는 하는데 나는 그런 생각은 못했다.
   그냥 재귀함수에 마지막 집의 색을 줘서 처음 집의 색이 같으면 큰 수를 줘버렸다.

문제풀이 소감

두번 틀렸는데 그 이유는 세번 반복할때 초기화를 안해줬다.
마지막 집의 색이 무엇이냐에 따라 값이 바뀐다는 사실을 인지하지 못했었다.
다행히 반례를 금방 찾아서 해결했지만 자꾸 사소한 부분에서 실수한다.
연습량이 부족해서 그런 실수들을 하는 것 같다.
그래도 알고리즘 실력이 많이 늘은게 느껴진다. 다만 연습량을 채우기 위해 dp문제를 많이 풀어볼 예정이다.

소스

#include <iostream>
#include<algorithm>
using namespace std;
int n;
int h[1001][3] = { 0 };
int d[1001][3] = { 0 };
bool visited[1001][3] = { 0 };
int solve(int n, int color, int first) {
	if (n == 1)
	{
		if (color == first) {
			return 20000000;
		}
		else
			return h[n][color];
	}
	if (visited[n][color])
		return d[n][color];
	visited[n][color] = true;
	if (color == 0) {
		d[n][0] = min(solve(n - 1, 1, first), solve(n - 1, 2, first)) + h[n][color];
	}
	if (color == 1)
	{
		d[n][1] = min(solve(n - 1, 0, first), solve(n - 1, 2, first)) + h[n][color];
	}
	if (color == 2)
	{
		d[n][2] = min(solve(n - 1, 0, first), solve(n - 1, 1, first)) + h[n][color];
	}
	return d[n][color];
}
int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			cin >> h[i][j];
	int ans = 2000000;
	if (n == 1)
	{
		ans = min(min(h[1][0], h[1][1]), h[1][2]);
	}
	else {
		for (int k = 0; k < 3; k++)
		{
			for (int i = 0; i <= n; i++)
				for (int j = 0; j < 3; j++)
					visited[i][j]=0;
			ans = min(ans, solve(n, k, k));
		}
	}
	cout << ans;
}