[210422][백준/BOJ] 1149번 RGB거리

문제

입출력

풀이

dp로 문제를 해결할 수 있으며 i번째 집을 빨강, 초록, 파랑으로 칠했을 때의 최소 비용을 구하는 문제이다.

비용을 저장하기 위한 배열 d[1001][3]을 선언한다.
d[i][0] 에는 i번째 집을 빨강색으로 칠할때의 최소비용을
d[i][1] 에는 i번째 집을 초록색으로 칠할때의 최소비용을
d[i][2] 에는 i번째 집을 파란색으로 칠할때의 최소비용을 저장한다.

d[i]집이 빨강색일려면 이전 집이 초록색이거나 파란색이어야하고
파란색일려면 이전 집이 빨강색이거나 초록색이어야하고
초록색일려면 이전 집이 빨강색이거나 파란색이어야한다.

코드

#include <bits/stdc++.h>
using namespace std;

int d[1002][3];
int r[1002], g[1002], b[1002];

int dp(int n)
{
	d[1][0] = r[1];
	d[1][1] = g[1];
	d[1][2] = b[1];
	
	for (int i = 2; i <= n; ++i)
	{
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + r[i];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + g[i];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + b[i];
	}
	return min({ d[n][0], d[n][1], d[n][2] });
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i)
		cin >> r[i] >> g[i] >> b[i];
	
	cout << dp(n);
}