[BOJ] 1149_RGB거리 with cpp

# 생각

색깔이 3가지이므로 2차원 배열을 적용한 DP를 활용하면 쉽게 해결할 수 있다

 

d[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 빨강

d[i][1] = i번째 집까지 칠할 때 비용의 최솟값, 초록

d[i][2] = i번째 집까지 칠할 때 비용의 최솟값, 파랑

 

점화식은

k번째 집을 빨강으로 칠할 예정이라면, k-1번째는 초록이나 파랑이어야만 하고

둘 중에 최소인 값을 가져오면 된다

그러므로 d[k][0] = min(d[k-1][1], d[k-1][2]) + R[k]가 된다(R[k] = k번째 집을 빨강으로 칠할 때 드는 비용)

 

 

# 전체 코드

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

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> r[i] >> g[i] >> b[i];
	}
	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];
	}
	cout << min({ d[n][0], d[n][1], d[n][2] });
}

 

---

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

1149번: RGB거리