백준 1149번: RGB거리

[문제 링크]

1149번: RGB거리

---

https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제라고 생각한다.

 

N번째 집이 어떤 색으로 칠해진다면 N+1번째 집은 N번째 집이 칠해진 색깔을 제외한 색깔로 칠해져야 한다는 사실과 

N+1번째 집이 칠해진 색깔에 따라 N+2번째 집이 칠해지는 색깔도 정해진다는 사실을 생각한다면 어렵지 않게 풀이법을 떠올릴 수 있을 것이다.

 

동적계획법 문제는 Top-Down과 Bottom-Up으로 알고리즘을 구현할 수 있는데, 각각의 방식마다 장점과 단점이 존재한다.

필자는 두 가지 방식을 연습하기 위하여 Top-Down과 Bottom-Up 각각 구현하였다.

---

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int house[1001][3], memo[1001][3];

inline int min(int a, int b) { return a < b ? a : b; }

int TopDown(int here, int color)
{
	if (here == 0) return house[here][color];

	int& ret = memo[here][color];
	if (ret != -1) return ret;

	ret = INF;

	for (int i = 0; i < 3; i++)
	{
		if (i == color) continue;
		ret = min(ret, TopDown(here - 1, i) + house[here][color]);
	}

	return ret;
}

int BottomUp(int N)
{
	memo[0][0] = house[0][0];
	memo[0][1] = house[0][1];
	memo[0][2] = house[0][2];

	for (int i = 1; i < N; i++)
		for (int j = 0; j < 3; j++)
		{
			int cost = house[i][j];
			if (j == 0) 
				memo[i][j] = min(cost + memo[i - 1][1], cost + memo[i - 1][2]);
			else if (j == 1) 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][2]);
			else 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][1]);
		}

	return min(memo[N - 1][0], min(memo[N - 1][1], memo[N - 1][2]));
}
int main(void)
{
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> house[i][j];

	// Top-Down
	int res = INF;
	for (int i = 0; i < 3; i++)
		res = min(res, TopDown(N - 1, i));		
	cout << res << endl;
	
	// Bottom-Up
	cout << BottomUp(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 63 day