[백준] 동적계획법1 RGB 거리 java 자바

문제

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

1149번: RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

풀이

연달아서 같은 색을 칠할 수 없다. 먼저 가장 처음 집은 이전에 칠한 기록이 없기 때문에 cost값으로 초기화 해준다. 그 다음부턴

cost[N][0]+min(dp[N-1][1], dp[N-1][2])

cost[N][1]+min(dp[N-1][0], dp[N-1][2])

cost[N][2]+min(dp[N-1][0], dp[N-1][1])

이렇게 각 색깔별로 점화식을 세워준다.

즉 점화식은 다음과 같다.(n은 집, c는 색상)

(n=0, c=0,1,2) dp[n][c]=cost[n][c]

(n>0, c=0) dp[n][c]=cost[n][0]+min(dp[n-1][1], dp[n-1][2])

(n>0, c=1) dp[n][c]=cost[n][1]+min(dp[n-1][0], dp[n-1][2])

(n>0, c=2) dp[n][c]=cost[n][2]+min(dp[n-1][0], dp[n-1][1])

 

코드

import java.util.*;
public class Main {

	static int[][]dp;
	static int[][]cost;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		
		dp=new int[N][3];
		cost=new int[N][3];
		for(int i=0;i<N;i++) {
			cost[i][0]=sc.nextInt();
			cost[i][1]=sc.nextInt();
			cost[i][2]=sc.nextInt();
		}
		
		dp[0][0]=cost[0][0];
		dp[0][1]=cost[0][1];
		dp[0][2]=cost[0][2];
		
		System.out.println(Math.min(CalcCost(N-1, 0), Math.min(CalcCost(N-1,1), CalcCost(N-1,2))));
		
	}

	public static int CalcCost(int N, int c) {
		if(dp[N][c]==0) {
			if(c==0)
				dp[N][0]=Math.min(CalcCost(N-1,1), CalcCost(N-1, 2))+cost[N][0];
			else if(c==1)
				dp[N][1]=Math.min(CalcCost(N-1,0), CalcCost(N-1, 2))+cost[N][1];
			else
				dp[N][2]=Math.min(CalcCost(N-1, 0), CalcCost(N-1, 1))+cost[N][2];
		}
		
		return dp[N][c];
	}
}

 

 

결과

굿