[백준] 1149번 : RGB거리 [C/C++]

#문제

1149번: RGB거리

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

1149번: RGB거리

 

---

#접근방법

거리에 있는 N개의 집들을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집이 서로 다른 색으로 칠하도록 하며 모든 집을 칠하는 비용의 최솟값을 구해야 한다.

 

이전 배열의 값을 계속 사용하는 다이나믹 프로그래밍 기법을 사용하여 최솟값을 누적시키면서 풀면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int dp[1005][3];

int main(){
	int n;
	int ans;
	
	scanf("%d",&n);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<3;j++)
			scanf("%d",&dp[i][j]);
	
	for(int i=1;i<n;i++){
		dp[i][0] += min(dp[i-1][1],dp[i-1][2]);
		dp[i][1] += min(dp[i-1][0],dp[i-1][2]);
		dp[i][2] += min(dp[i-1][0],dp[i-1][1]);
	}
	
	ans = min({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
	
	printf("%d",ans);
	
	return 0;
}

 

두번 째 집을 R로 색칠을 하려면 첫번 째 집이 B또는 G로 색칠이 되어야 한다.

 

R로 색칠할 때 B또는 G로 색칠하는 비용중에 비용이 적은 것으로 색칠을 하면 최소비용으로 두번 째 집을 R로 색칠할 수 있다.

 

따라서 N번 째 집을 RGB중 하나로 색칠을 할 때, N-1번 째 집에서 N번 째에 색칠된 동일한 색과는 다른 색 2가지 중 색칠하는 비용이 적은 것으로 선택하면 최소비용을 선택할 수 있다.

 

이 과정을 N까지 반복하면 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중 제일 작은 값이 정답이 된다.

---

#성능

---

#정리

N번 째 집을 색칠할 때, N-1번 째 집의 색 중에 동일한 색을 제외한 2가지 색의 칠하는 비용이 적은 것으로 선택하면 최소비용을 구할 수 있다는 사실을 알고 있고 이를 다이나믹 프로그래밍으로 구현 할 수 있으면 풀 수 있는 문제였다.