[BJ] 1149. RGB 거리

www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 

N개의 집을 R, G, B 색으로, 이웃과 색이 겹치지 않게 칠하는데 드는 최소 가격

→ R, G, B 3가지 방향으로 접근하여 N번째 까지 드는 비용을 각각 구한 후 3개 중 최소 가격 찾기

 

• 2번째 집을 칠할 때 가격 = 1번째 집 까지 칠한 가격 + 2번째 집을 칠한 가격
• 3번째 집을 칠할 때 가격 = 2번째 집 까지 칠한 가격 + 3번째 집을 칠한 가격
• d[i] = d[i-1] + 최소값 map[i]
• 이전 번째 집을 최소값으로 칠했다고 (d[i-1])해서 무조건 다음 집을 최소로 칠할 수 있는 것은 아님
  → 1. 첫번째 집을 R로
  2. 첫번째 집을 G로
  3. 세번째 집을 B로 칠할 경우 모두 고려하여 N번째 까지 계산해야 한다.
• i번째 집은 i-1번째 집과 같은 색으로 칠할 수 없다.
  d[i][0] = Min(d[i-1][1], d[i-1], [2]) + a[i][0])
d[i][1] = Min(d[i-1][0], d[i-1], [2]) + a[i][1])
d[i][2] = Min(d[i-1][1], d[i-1], [2]) + a[i][2])
• d[0][]인 값이 사용된다.
  d[0][0] = d[0][1] = d[0][2]= 0;

 

import java.io.*;
import java.util.*;
// 210323

public class Main_BJ_1149_RGB거리 {
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = stoi(br.readLine().trim());
		
		int[][] map = new int[N+1][3];
		int[][] d = new int[N+1][3];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j=0; j<3; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		
		// d[0][] 초기화
		d[0][0] = d[0][1] = d[0][2] = 0;
		for(int i=1; i<=N; i++) {
			// R
			d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + map[i][0];	
			// G
			d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + map[i][1];
			// B
			d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + map[i][2];
		}
		
		// i==N에서 최소값 찾기
		int min = Integer.MAX_VALUE;
		for(int j=0; j<3; j++) {
			if(min>d[N][j]) min=d[N][j];
		}
		
		System.out.println(min);
		br.close();
	}
}