BaekJoon _ 백준 1149 > DP> #34 RGB 거리

RGB 거리

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

알고리즘 종류: DP algorithm

1. 문제설명

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

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

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

2. 나의 코드

1) DP문제라고 해서 풀었는데, 어쩌다보니 Top-Down 방식으로 푼 문제..ㅠ(* 시간초과*)

- level은 현재 주어진 집의 총 갯수

- cost배열은 각 레벨에서 주어진 집을 칠할때 드는 RGB 각각의 비용을 저장하는 배열이다.

- class RGB의 findrgb()는 level을 하나씩 올리면서 해당 레벨에 있는 색깔의 비용 중 promising 한 것만 찾아서 Minimum을 찾는 함수이다.

- 처음 level(=0)에는 promising과 상관없이 3가지 다 칠해볼 수 있으므로 세가지를 다 구해보기 위해 findrgb(0,-1)을 사용한다.

- 구현은 재귀적으로 구현했다.

- 종료 조건으로 마지막 레벨에 도착 했을때, 마지막 레벨의 minimum값을 리턴하도록 만들었다.

import java.util.*;

class Main{
	public static void main(String [] args){
			Scanner sc = new Scanner(System.in);
			int level = sc.nextInt();
			int mincost=0;
			int [][] cost = new int[level][3];
			for(int i=0;i<level;i++){
				for(int j=0;j<3;j++){
					cost[i][j] = sc.nextInt();
				}
			}
			RGB rgb = new RGB(level,cost);
			mincost = rgb.findRgb(0,-1);
			System.out.println(mincost);
		}
	}

class RGB{
		int [][] cost;
		int level;
		public RGB(int level,int [][] cost){
			this.cost = cost;
			this.level = level;
		}

		public int findRgb(int lev,int num){
			int findedsum = 0;
			int min = 0;
			if(lev == level-1){
				for(int i=0; i<2; i++){
					if(isPromising(num,i)){
						for(int j=i+1;j<3;j++){
							if(isPromising(num,j))
								min =	Math.min(cost[lev][i], cost[lev][j]);
							}
						}
					}
					return min;
				}

			if(num == -1){
				findedsum = Math.min(cost[lev][0]+ findRgb(lev+1, 0),cost[lev][1] + findRgb(lev+1, 1));
				findedsum = Math.min(findedsum,cost[lev][2]+ findRgb(lev+1, 2));
			}

			else{
				for(int i=0; i<2; i++){
					if(isPromising(num,i)){
						for(int j=i+1;j<3;j++){
							if(isPromising(num,j))
								findedsum =	Math.min(cost[lev][i] + findRgb(lev+1, i), cost[lev][j] + findRgb(lev+1, j));
							}
						}
					}
				}
			return findedsum;
		}

		public boolean isPromising(int preindex, int index){
			if(preindex == index)
				return false;
			else
				return true;
		}
	}

2) DP 문제라고 풀었는데, 순 노가다로 풀었지만 틀린 문제..(*반례가 있음*)

- 반례를 찾지 못함... 예시 문제는 다 풀리는데...

- 위와 비슷하게 풀었지만, 재귀를 사용하지 않은 문제이다.

- level은 현재 주어진 집의 총 갯수

- cost배열은 각 레벨에서 주어진 집을 칠할때 드는 RGB 각각의 비용을 저장하는 배열이다.

- level 만큼 반복하는 for문 안에서 해당 level의 minimum값을 찾는다. 

- 이전에 저장된 index값과 for문의 j(현재 인덱스 값)과 같으면, non-promising이므로 제끼고 다음 연산을 진행한다.

- temp라는 변수에 저장된 min값의 인덱스를 저장하고,  for문이 끝나면 index값에 다시 min값을 저장한다.

import java.util.*;

class Main{
	public static void main(String [] args){
			int index;
			int temp = 0;
			int sum = 0;
			int answer = 0;
			int MIN = 1001;
			Scanner sc = new Scanner(System.in);
			int level = sc.nextInt();
			int mincost=0;
			int [][] cost = new int[level][3];

			for(int i=0;i<level;i++){
				for(int j=0;j<3;j++){
					cost[i][j] = sc.nextInt();
				}
			}

			for(int h=0;h<3;h++){
				sum = cost[0][h];
				index = h;
				for(int i=1; i<level; i++){
						for(int j=0;j<3;j++){
							if(MIN > cost[i][j] && index != j){
								MIN = cost[i][j];
								temp = j;
							}
						}
						sum += MIN;
						index = temp;
						MIN = 1001;
					}
				if(h==0){
					answer = sum;
				}
				else{
					if(answer > sum)
						answer = sum;
				}
			}
			System.out.print(answer);
		}
}

3. 다른 사람 코드

- 진정한 DP문제

import java.util.*;
class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int i,j;
		int n = sc.nextInt();
		int d[][] = new int[n+1][3];
		int a[][] = new int[n+1][3];

		for(i=1;i<=n;i++)
			for(j=0;j<3;j++)
				a[i][j] = sc.nextInt();

		d[0][0] = d[0][1] = d[0][2] = a[0][0] = a[0][1] = a[0][2] =0;
		for(i=1;i<=n;i++){
			d[i][0] = Math.min(d[i-1][1],d[i-1][2]) + a[i][0];
			d[i][1] = Math.min(d[i-1][0],d[i-1][2]) + a[i][1];
			d[i][2] = Math.min(d[i-1][0],d[i-1][1]) + a[i][2];
		}

		System.out.println(Math.min(Math.min(d[n][0],d[n][1]), d[n][2]));
		sc.close();
	}
}

4. 보완

DP 문제만 조져야겠다.

점화식 찾는게 제일 힘든 것 같다.