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 문제만 조져야겠다.
점화식 찾는게 제일 힘든 것 같다.
