[백준 1149 C++] RGB 거리

오늘은 백준(BOJ) 1149번 RGB 거리 문제에 대해 다뤄볼 예정이다.

RGB 거리 문제 링크 (백준(BOJ) 1149번 문제): https://www.acmicpc.net/problem/1149 

1149번: RGB거리

문제 설명 

백준 1149번 RGB 거리 문제는 N개의 집을 색칠하려고 하는데 현재 집이 i 번째라고 했을 때 이웃 간( i -1 또는 i + 1)의 집과 색깔이 다르면서 최소 값을 구하는 문제이다. 

문제 풀이 

백준 1149번 RGB 거리 문제의 제약 조건을 통해, 얻을 수 있는 정보는 현재 집이 이전 집의 색깔과 다르면서 최소 값을 구해주는 것이다. 단, 이 문제는 시간이 0.5초 내에 해결되어야 하므로 DP(Dynamic Progrmming) 알고리즘을 사용하여 해결해주어야 한다. 

(DP의 장점: 특정 케이스의 결과 값을 저장하고 있어 이미 계산된 경우 반복적으로 계산하지 않아도 된다.) 

 

이를 소스코드로 나타내면 아래와 같다. 

 

	#include <iostream>
	#include <algorithm>
	#include <string.h>
	using namespace std ;
	int result = 1e8, n = 0 ;
	int rgb[1000][3];
	int rgb_dp[1000][3];
	int DP(int k, int pre) {
	if( k == n) return 0;
	if( rgb_dp[k][pre] != -1) return rgb_dp[k][pre];
	int r = 1e8;
	for(int i = 0; i < 3; i++) {
	if( pre != i) {
	r = min( r, rgb[k][i] + DP(k+1, i));
	}
	}
	rgb_dp[k][pre] = r;
	return r;
	}
	int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(rgb_dp, -1, sizeof(rgb_dp));
	cin >> n;
	int a,b,c;
	for(int i = 0 ; i < n; i++) {
	cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
	}
	result = min(result, rgb[0][0] + DP(1, 0));
	result = min(result, rgb[0][1] + DP(1, 1));
	result = min(result, rgb[0][2] + DP(1, 2));
	cout << result << '\n';
	return 0 ;
	}

view raw 1149.cpp hosted with ❤ by GitHub