백준 1149번- RGB거리

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include <numeric>
#include<math.h>
using namespace std;

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

처음에 짠소스가 안풀려 반례를 찾아보던 중

3

1 20 30 

50 5 6 

9 3 7

정답:10

정답이 13 이라면 왜 그럴까?  

생각해 볼 수 있는 좋은 문제지 않나 싶습니다

이런 글을 보게 되었고 그리디 알고리즘 처럼 구현했다는걸 깨닫고 DP로 생각해보려고 노력을 했더니 간단한 소스로 풀게 되었다.

 

---삽질--

목표: cost
R  G  B
입력  입력  입력
i를 기준으로 i+1의 부분을 찾을시 i+1의 부분에서 중복된 값이 있다고 하면 처리가 이상하게 됨
i를 기준으로 i-1 부분을 보면 중복 처리 가능 1부터시작