[백준 / BOJ] 1149번: RGB거리

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

1149번: RGB거리

 

 

---

 

코드

---

#include <cstdio>
#include <algorithm>
using namespace std;

int rgb[1001][3] = {0,};


int main() {
	int cost[3], n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &cost[0], &cost[1], &cost[2]);
		rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + cost[0];
		rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + cost[1];
		rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + cost[2];

	}
	int res = (rgb[n - 1][0] < rgb[n-1][1] ? min(rgb[n - 1][0], rgb[n - 1][2]) : min(rgb[n - 1][1], rgb[n - 1][2]));
	//int res = min(rgb[n - 1][2], min(rgb[n - 1][0], rgb[n - 1][1]));
	printf("%d\n", res);
	return 0;
}

 

 

 

---

 

 

N의 최대 입력이 1,000 이므로 동적 계획법으로 문제를 해결하면 아주 짧은 시간 내에(시간복잡도 O(N)) 풀 수 있는 문제이다.

각 줄마다 r, g, b에 관한 비용을 모두 구해줘야 문제를 풀 수 있겠다는 생각을 했다. i번째 집에서의 각 색깔 별 최소비용은 (i번째 집의 특정 색깔에 대한 비용) + (i-1번째 집의 나머지 두 색깔에 대한 최소비용 중 작은 값)이라는 단계별 풀이를 도출할 수 있었다. 마지막 집에 대해서 r, g, b 각각에 대해 계산된 비용 중 가장 작은값을 출력하기 위해 삼항 연산자를 사용했는데, 다른 사람들의 코드를 보다가 굳이 나처럼 하지 않고 min함수만을 이용해서 구현할 수 있다는 것을 알았다. 좋은것 같아서 나중에 필요하면 잊지 않고 쓸 수 있도록 주석으로 적어놨음..!