BOJ 1149번 :: RGB거리

#문제

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

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

입력

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

출력

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

 

#작성 코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int N;
int house[1001][3];
int tmp[3];		// 현재까지 선택의 최솟값들 저장. 
int choice[3];

int answer(){
	tmp[0] = house[1][0];	// 첫번째 집에서 빨강 선택 
	tmp[1] = house[1][1];	// 첫번째 집에서 초록 선택 
	tmp[2] = house[1][2];	// 첫번째 집에서 파랑 선택 
	
	// 두번째 집부터 마지막 집까지 순회 
	for(int num=2; num<=N; num++){
		// 새 집에서 빨강 선택 <- 이전 집에서 초록, 파랑 선택한 결과 중 작은것 
		choice[0] = house[num][0]+min(tmp[1], tmp[2]); 
		// 새 집에서 초록 선택 <- 이전 집에서 빨강, 파랑 선택한 결과 중 작은것
		choice[1] = house[num][1]+min(tmp[0], tmp[2]);
		// 새 집에서 파랑 선택 <- 이전 집에서 빨강, 초록 선택한 결과 중 작은것
		choice[2] = house[num][2]+min(tmp[0], tmp[1]);
		
		// 각 결과들을 재사용할 수 있도록 저장. 
		tmp[0] = choice[0];
		tmp[1] = choice[1];
		tmp[2] = choice[2];
	}
	
	// 모든 집을 순회한 후, 제일 마지막 집에서 빨강, 초록, 파랑 선택한 누적 결과 중 최솟값 리턴 
	return min(min(tmp[0], tmp[1]), tmp[2]);
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		// 각 집을 빨강, 초록, 파랑으로 칠하는 비용 
		scanf("%d %d %d", &house[i][0], &house[i][1], &house[i][2]);
	}
	printf("%d\n", answer());
	return 0;
}

##

집의 수 N은 최대 1000, 각 집에 칠할 수 있는 R, G, B 비용 ->int  house[1001][3]배열을 선언

#191216 review

아래의 코드처럼 1~i번째 집을 칠하는 비용을 저장하는 배열을 추가 선언하여도 메모리 상에서 크게 차이나지않는다.

2008kb를 사용한 코드가 아래의 코드이다

#include <iostream>
using namespace std;
 
/* 1149 RGB 거리 */
int rgb_n;
int rgb_cost[1001][3];        // [0]:r, [1]:g, [2]:b 비용 
int rgb[1001][3];        // [1]집~[i]집까지 [r/g/b]로 칠하는 비용
void rgb_input(){
    cin>>rgb_n;
    for(int i=1; i<=rgb_n; i++){
        cin>>rgb_cost[i][0]>>rgb_cost[i][1]>>rgb_cost[i][2];
    }
}
void rgbsolve(int rgb_n){
    for(int i=0; i<3; i++){
        rgb[1][i] = rgb_cost[1][i];
    }
    for(int i=2; i<=rgb_n; i++){
        rgb[i][0] = rgb_cost[i][0]+min(rgb[i-1][1], rgb[i-1][2]);
        rgb[i][1] = rgb_cost[i][1]+min(rgb[i-1][0], rgb[i-1][2]);
        rgb[i][2] = rgb_cost[i][2]+min(rgb[i-1][0], rgb[i-1][1]);
    }
    cout<<min(min(rgb[rgb_n][0], rgb[rgb_n][1]), rgb[rgb_n][2])<<'\n';
    return;
} 
int main(){
    /* 1149 RGB 거리 */
    rgb_input();
    rgbsolve(rgb_n);
    return 0; 
}