[백준 1149] RGB거리

[문제 바로가기]👇

1149번: RGB거리

 

 

풀이

현재 집이 옆집의 색과 같으면 안된다는 규칙이 있어서 각 집을 RGB색으로 각각 칠했을 때의 비용을 모두 저장해서 비교를 했다

규칙 찾기

• 현재 집이 이전 집과 색이 다르다면 집을 칠하는 규칙을 만족하기 때문에 이전 집, 다음 집 모두가 아니라 이전 집과만 색 비교를 해도 가능
• 현재 집이 R색을 칠했다면, 이전 집은 G,B색 중 최솟값을 칠한 비용 + 현재 집이 R색을 칠했을 때 비용
• 현재 집이 G색을 칠했다면, 이전 집은 R,B색 중 최솟값을 칠한 비용 + 현재 집이 G색을 칠했을 때 비용
• 현재 집이 B색을 칠했다면, 이전 집은 R,G색 중 최솟값을 칠한 비용 + 현재 집이 B색을 칠했을 때 비용

 

 

전체 코드

package Day_0328;

import java.io.*;
import java.util.*;

public class Main_bj_1149_RGB거리_서울_20반_김선희 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 각 색을 칠하는데 필요한 비용 - 0:R, 1:G, 2:B 
		int[][] cost = new int[N+1][3];
		for(int i=1; i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			cost[i][0] = Integer.parseInt(st.nextToken());
			cost[i][1] = Integer.parseInt(st.nextToken());
			cost[i][2] = Integer.parseInt(st.nextToken());
		}
		
		// n번째 집까지 각 색으로 칠하는 비용
		// 0 : n번째 집을 R색으로 칠할 때 비용
		// 1 : n번째 집을 G색으로 칠할 때 비용
		// 2 : n번째 집을 B색으로 칠할 때 비용
		int[][] dp = new int[N+1][3];
		
		dp[1] = cost[1];
		for(int i=2; i<=N; i++) {
			//i번째 집을 R색으로 칠하기 때문에 i-1번째는 R색이 아니어야 함 >> G,B색으로 칠한 것 중 최소값
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0]; 
			
			//i번째 집을 G색으로 칠하기 때문에 i-1번째는 G색이 아니어야 함 >> R,B색으로 칠한 것 중 최소값
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
			
			//i번째 집을 B색으로 칠하기 때문에 i-1번째는 B색이 아니어야 함 >> R,G색으로 칠한 것 중 최소값
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
		}
		
		// n번째 집을 RGB색으로 각각 칠했을 때 중 최솟값 찾기
		System.out.println(Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2])));
		br.close();
	}
}