[백준] 1149번 : RGB 거리

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1번 집부터 n번 집까지 각각 빨강, 초록, 파랑색으로 칠했을 때의 최소 비용을 2차원 배열 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

1) 2차원 벡터인 costs를 선언해 각 집에 대해 R, G, B로 칠할 때의 비용을 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, dp[1][0], dp[1][1], dp[1][2]를 각각 costs[1][0], costs[1][1], costs[1][2]로 초기화한다.

• dp[i][j] : i 번째 순서 집을 j 색으로 칠했을 때의 최소 비용
  • dp[1][0] : 1 번째 집을 R로 칠할 때 최소 비용
  • dp[1][1] : 1 번째 집을 G로 칠할 때 최소 비용
  • dp[1][2] : 1 번째 집을 B로 칠할 때 최소 비용

3) i가 2 ~ n일 때까지 경우의 수를 전부 갱신한다.

• 주어진 규칙에 의해 현재 순서 집은 이전 순서 집과 같은 색일 수 없음.
  • 만약 현재 순서 집을 R로 칠할 때의 비용을 구한다면
    • 이전 순서 집을 G 또는 B로 칠하는 경우의 최소 비용 + 현재 순서 집을 R로 칠하는 비용
      • 두 경우 중 더 작은 값이 최소 비용이 된다.
  • 현재 순서 집을 G, B로 칠할 때의 비용도 위와 마찬가지로
    • 현재 순서 집의 색과 다른 두 색으로 이전 순서 집을 칠했을 경우 중 더 작은 값 + 현재 순서 집을 칠하는 비용이 된다.
• 위 과정을 점화식으로 나타내면
  • dp[i][0] = min(dp[i][1], dp[i][2]) + costs[i][0]
  • dp[i][1] = min(dp[i][0], dp[i][2]) + costs[i][1]
  • dp[i][2] = min(dp[i][0], dp[i][1]) + costs[i][2]

4) 따라서 2부터 n까지 모든 i에 대해 각 색으로 칠하는 최소 비용을 차례대로 구하면 최종적으로
dp[n][0], dp[n][1], dp[n][2]에 저장되는 값 중 가장 작은 값이 최소 비용이 된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int dp[1001][3];	// dp[i][j] : i번째 집에서 j색으로 칠했을 때의 최소 비용
vector<vector<int>> costs;

void solution()
{
	for (int i = 0; i < 3; i++)
		dp[1][i] = costs[1][i];

	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
	}

	cout << min({ dp[n][0], dp[n][1], dp[n][2] });
}

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

	cin >> n;
	costs.resize(n + 1);

	for (int i = 0; i < n; i++)
		costs[0].push_back(0);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int cost;
			cin >> cost;
			costs[i].push_back(cost);
		}
	}
	solution();
}