[백준 : 1149번 RGB거리]

오늘은 백준에서 동적계획법(Dynamic Programming : DP)를 사용해서

1149번 문제인 RGB거리를 풀어보겠습니다.

자세한 내용은 아래를 보시죠!

RGB거리 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

36337

16626

12507

46.834%

문제

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

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

입력

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

출력

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

예제 입력 1

3 26 40 83 49 60 57 13 89 99

예제 출력 1

96

 

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

1149번: RGB거리

 

제 코드는 아래와 같고 내용은 주석을 확인해 주세요~

 

#include <iostream>
#include <math.h>
using namespace std;

int d[1001][3];	 // n번째 집을 빨, 초, 노로 칠할때 각각 최소 비용   
unsigned int p[1001][3];	// n 번째 집을 빨 , 초 , 노 로 칠하는 각각 가격 배열

int MIN(int a,int  b) {	// int 2 개 중에 작은 값
	if (a <= b) {
		return a;
	}
	else return b;

}

int MIN3(int a, int b, int c) {	//int 3개 중에 작은 값
	
	int min = 0;
	
	min = MIN(a, b);

	min = MIN(min, c);

	return min;
}

int main() {

	ios_base::sync_with_stdio(false);

	int test;
	cin >> test;

	d[0][0] = d[0][1] = d[0][2] = p[0][0] = p[0][1] = p[0][2] = 0;	//집의 갯수를 1부터 시작하기 위해 d[1001][3]으로 선언 했으므로 집의 수가 0일 때는 0으로 초기화 함 

	for (int i = 1; i <= test; i++) {

		cin >> p[i][0] >> p[i][1] >> p[i][2];	// 각 집마다 빨, 초, 녹으로 칠했을 경우 드는 비용을 저장

	}

	
	for (int i = 1; i <= test; i++) {

		d[i][0] = p[i][0] + MIN(d[i - 1][1], d[i - 1][2]);	//i번째 집을 빨로 칠함 =  i-1번째 집을 초록과 파랑으로 칠하는 두 값 중 작은 값 + i번째 집을 빨간색으로 칠하는 값
		d[i][1] = p[i][1] + MIN(d[i - 1][0], d[i - 1][2]);	//i번째 집을 초로 칠함 =  i-1번째 집을 빨강과 파랑으로 칠하는 두 값 중 작은 값 + i번째 집을 초록색으로 칠하는 값
		d[i][2] = p[i][2] + MIN(d[i - 1][0], d[i - 1][1]);	//i번째 집을 파로 칠함 =  i-1번째 집을 빨강과 초록으로 칠하는 두 값 중 작은 값 + i번째 집을 파란색으로 칠하는 값
		
	}


	cout << MIN3(d[test][0], d[test][1], d[test][2]);	// test번째 집을 빨, 초, 파로 칠하는 값 중에 최소값


	return 0;
}

 

과거에 풀었던 문제들을 올리는 거라 채점에 문제가 있다면 말씀해 주세요~