[백준, BOJ 1149] RGB거리 (java)

출처-https://www.acmicpc.net/problem/1149

1149번: RGB거리

---

728x90

 

내 생각 :

color[i][0]에는 각 집에 빨강으로 칠하는 비용
color[i][1]에는 각 집에 초록으로 칠하는 비용
color[i][2]에는 각 집에 파랑으로 칠하는 비용
을 저장한다.

dp[i][0]에는 dp[i-1][1]와 dp[i-1][2] 둘 중 +color[i][0]을 했을 때 더 작은 수,
dp[i][1]에는 dp[i-1][0]와 dp[i-1][2] 둘 중 +color[i][1]을 했을 때 더 작은 수,
dp[i][2]에는 dp[i-1][0]와 dp[i-1][1] 둘 중 +color[i][2]을 했을 때 더 작은 수
를 저장한다.

그리고 dp[n][0], dp[n][1], dp[n][2] 중 작은 수 출력

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner (System.in);
		int n=scan.nextInt();
		int color[][]=new int[n+1][3];
		int dp[][]=new int[n+1][3];
		
		for (int i=1; i<=n;i++) {
			color[i][0]=scan.nextInt();
			color[i][1]=scan.nextInt();
			color[i][2]=scan.nextInt();
		}
		
		for (int i=1;i<=n;i++) {
			dp[i][0]=color[i][0]+dp[i-1][1];
			if (dp[i][0]>color[i][0]+dp[i-1][2])
				dp[i][0]=color[i][0]+dp[i-1][2];
			dp[i][1]=color[i][1]+dp[i-1][0];
			if (dp[i][1]>color[i][1]+dp[i-1][2])
				dp[i][1]=color[i][1]+dp[i-1][2];
			dp[i][2]=color[i][2]+dp[i-1][0];
			if (dp[i][2]>color[i][2]+dp[i-1][1])
				dp[i][2]=color[i][2]+dp[i-1][1];
		}
		
		int min=dp[n][0];
		for (int i=1;i<3;i++)
			if (dp[n][i]<min)
				min=dp[n][i];
		
		System.out.println(min);
	}

}