1149번 : RGB거리 [DP, JAVA]

 

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

1149번: RGB거리

대표적인 DP 문제라고 한다.

 

문제를 한 문장으로 정의하자면

' N개의 집을 이웃집과 색이 겹치지 않게 칠하는데 드는 최소가격'을 구하는 문제이다.

dp[i][] : i 집까지의 최소 cost로 정했다.

 

일단 dp[i][0]은 i번째 집을 빨간색으로 하는 최소 가격이다. 

dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2])+cost[i][0] 의 의미는 이러하다.

i번째 집은 빨간색을 선택한다. -> cost[i][0]

그러므로 그 집을 선택하기 전 집(앞쪽에 이웃한 집)은 다른 색을 선택해야 한다. -> dp[i-1][1], dp[i-1][2]

최소 가격을 구해야 하므로 이전 집이 초록, 파랑을 선택한 경우 중 가격이 작은 경우를 더해준다.-> Math.min()

 

이것을 i번째 집이 각 색깔을 선택하는 3가지 경우로 나누어 계산해주고

마지막에 또 최소값을 구해서 출력해주었다.

 

코드

import java.util.Scanner;

public class Main {

static int MIN = Integer.MAX_VALUE;

static int cost[][];

static int dp[][];

 

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scan = new Scanner(System.in);

 

int N = scan.nextInt();

cost = new int[N+1][3]; //R,G,B

dp = new int[N+1][3];

 

for(int i=1;i<=N;i++)

for(int j=0;j<3;j++)

cost[i][j] = scan.nextInt();

 

dp[0][0] = dp[0][1] = dp[0][2] = 0;

cost[0][0] = cost[0][1] = cost[0][2] = 0;

 

for(int i=1;i<=N;i++) {

dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2])+cost[i][0];

dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2])+cost[i][1];

dp[i][2] = Math.min(dp[i-1][1], dp[i-1][0])+cost[i][2];

}

 

MIN = Math.min(Math.min(dp[N][0], dp[N][1]),dp[N][2]);

System.out.println(MIN);

}

}