ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 1149 RGB거리 (C++)

Posted on Feb 24, 2021 #동적프로그래밍(DP)   #Algorithm  

1149 | RGB거리

🙋‍♀️ 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

🙌 입출력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

🙋‍♂️ 예제 입출력

3
26 40 83
49 60 57
13 89 99

96

🚀 코드

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main() {
	cin >> n;
	int v[1001][3] = { 0 };
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &v[i][0], &v[i][1], &v[i][2]);
	}

	int dp[1001][3] = { 0 };
	// 각 색깔별로 첫 집의 색칠 비용을 넣고
	dp[0][0] = v[0][0];
	dp[0][1] = v[0][1];
	dp[0][2] = v[0][2];

	// 현재 집이 빨강이라면 앞 뒤 집은 무조건 파랑 과 초록중 하나
	for (int i = 1; i < n; i++) {
		dp[i][0] = v[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = v[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = v[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
	}

	printf("%d", min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
	return 0;
}

🌠 메모

다이나믹 프로그래밍 문제를 많이 풀어보지 않아서 처음 보고는 전혀 문제 풀이 방법이 떠오르지 않았다.

일단 문제의 조건때문에 더욱 헷갈렸다. 현재 집의 앞과 뒤가 모두 다른색(r-g-b 또는 g-b-r과 같이) i - 1과 i + 1의 색은 같을 수도 있는 것이었다. 따라서 현재 집을 기준으로 앞이든 뒤든 한 쪽의 집의 색만 신경쓰며 최소 비용을 구한다.

dp테이블에 비용을 기록하는데, 각각 0, 1, 2는 r, g, b색을 의미하며, i번째 집의 비용은 이전 집의 겹치지 않는 색 둘 중 하나의 최솟값을 현재 집의 비용과 더해서 구한다. 이때 어떤 색으로 칠했을 때 최소가 될 지 모르므로, 모든 색상의 경우를 구해야 하고, 이중 최솟값이 바로 답이 된다.

공부하고 있는 책의 문제와 더불어 많은 문제들을 풀어봐야 할 것 같다. 그리디 알고리즘이나 정렬같은 경우는 별도의 공부 없이도 쉽게 접근하고 문제풀이 방법을 떠올릴 수 있었지만, 이진탐색을 비롯하여 이번 다이나믹 프로그래밍 문제만 보아도 접해보지 않아서 코드를 짤 수가 없었다. 😓



# 카테고리