[C/C++] 코드업(codeup) 3501번 백준(BOJ) 1149번 RGB 거리

▽문제 바로가기(코드업)

https://codeup.kr/problem.php?id=3501

RGB 거리 (Small)

 

▽문제 바로가기(백준)

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

1149번: RGB거리

---

입력

첫째 줄에 집의 수 N이 주어진다.

N은 1,000보다 작거나 같다.

둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다.

비용은 1,000보다 작거나 같은 자연수이다.

 

출력

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

 

문제 풀이

 

평범한 동적계획법 문제입니다.

가짓수가 1000가지가 넘어가면 계산해야 하는 수가 많아지니 한 번만 계산하도록 메모이제이션기법을 사용하면 됩니다.

 

또한, 코드업은 RGB 거리 (Small)로 배열 개수가 작아서 동적계획법으로 풀지 않아도 되지만 백준의 경우 N이 1000까지 여서 반드시 동적계획법으로 풀어야 합니다. 그렇지 않으면 시간 초과가 뜹니다.

(N범위가 다르므로 배열 크기에 유념하여 코드업풀고 백준으로 넘어갔을 때 저처럼 고생 안 하시길...)

 

#include <stdio.h>

int n;
int arr[1001][3];
int memo[1001][3] = {0,};

int MIN(int a, int b){
	return a>b? b : a;
}

int recur(int now, int count){
	
	//현재 R, G, B 중 어떤색을 선택했느냐에 따라 나머지 두 가지 색 선택
	int a, b;
	if(now==0) a = 1, b = 2;
	if(now==1) a = 0, b = 2;
	if(now==2) a = 0, b = 1;
	
	//마지막에 도달하면 해당 값 리턴
	if(count==n-1){
		return arr[count][now];
	}
	
	//메모된값 있으면 메모값 리턴
	if(memo[count][now]!=0){
		return memo[count][now];
	}
	
	//두 가지경우를 모두 탐색해서 작은값 선택
	//그리고 메모
	else{
		return memo[count][now] = MIN(arr[count][now] + recur(a, count+1), arr[count][now] + recur(b, count+1));
	}
	
}


int main(){
	
	scanf("%d", &n);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	//처음에 R선택, G선택, B선택 중 가장 작은 값 찾기
	printf("%d", MIN(MIN(recur(0, 0), recur(1, 0)), recur(2, 0)));
	
	
	return 0;
}